Sachverhalt: A. X._ wird im Wesentlichen vorgeworfen, er habe ab September 2004 zu Unrecht eine Invalidenrente der Sozialversicherungsanstalt des Kantons Zürich (nachfolgend: SVA) sowie eine Komplementärrente der A._ Versicherungen (nachfolgend: A._) nach dem Bundesgesetz vom 20. März 1981 über die Unfallversicherung (UVG, SR 832.20) bezogen. Konkret habe er es unterlassen, die Versicherer über seine Arbeitstätigkeit als faktisch vollamtlicher Geschäftsführer der in Bratislava (Slowakei) domizilierten B._ GmbH orientiert zu haben. Überdies habe er in einem Fragebogen gegenüber der SVA sowie in einem protokollierten Gespräch mit der A._ wahrheitswidrige Angaben gemacht. Die A._ liess X._ nach einem telefonischen Hinweis sowie nach internen Vorabklärungen ab April 2007 observieren. Diese Beobachtungen mündeten in zwei Observationsberichte vom 29. September 2007 und 17. Dezember 2007. B. Das Bezirksgericht Dietikon verurteilte X._ am 10. Februar 2009 wegen mehrfachen Betrugs sowie versuchten Betrugs zu einer Freiheitsstrafe von 24 Monaten. Den Vollzug der Freiheitsstrafe schob es im Umfang von zwölf Monaten, bei einer Probezeit von drei Jahren, auf. Die übrigen zwölf Monate erklärte es unter Anrechnung von 87 Tagen Untersuchungshaft als vollziehbar. Die Zivilforderung der A._ verwies es auf den Zivilweg. Das Obergericht des Kantons Zürich sprach X._ am 24. März 2011 auf dessen Berufung hin frei. Auf die Zivilforderung der A._ trat es nicht ein. C. Die Oberstaatsanwaltschaft des Kantons Zürich erhebt Beschwerde in Strafsachen beim Bundesgericht. Sie beantragt, das Urteil des Obergerichts des Kantons Zürich aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. D. Das Obergericht des Kantons Zürich verzichtet auf eine Vernehmlassung. X._ beantragt, die Beschwerde der Oberstaatsanwaltschaft des Kantons Zürich sei abzuweisen, und ihm sei für das vorliegende Verfahren eine angemessene Prozessentschädigung zuzusprechen, sofern das Begehren um unentgeltliche Rechtspflege nicht bewilligt werde. 