Sachverhalt: A. Aufgrund anonymer Hinweise, Y._ handle im grossen Stil mit Partydrogen, unterzog die Stadtpolizei Zürich (StaPo) ihn am 6. April 2012 gegen 21.40 Uhr in der Zürcher Innenstadt einer Personen- und Effektenkontrolle, bei der sie acht Portionen Kokain (7.6 Gramm brutto) sowie 6.2 Gramm Marihuana sicherstellte. Y._ gab an, zur Untermiete bei X._ ein Zimmer zu bewohnen. Einer Hausdurchsuchung stimmte er nicht zu. Auf Ersuchen der StaPo ordnete die Staatsanwaltschaft telefonisch eine Hausdurchsuchung bei Y._ an. Noch am selben Abend wurden mit Hilfe eines Betäubungsmittel-Suchhundes die gesamte Wohnung an der Kraftstrasse 15 in 8044 Zürich sowie Estrich und Keller durchsucht. Hierbei konnten im Zimmer von Y._ verschiedene Betäubungsmittel, zahlreiche Betäubungsmittelutensilien und Fr. 1'500.-- Bargeld sichergestellt werden. In der Küche fand die StaPo eine Marihuana-Mühle, Minigrips mit verschiedenen Betäubungsmittelrückständen sowie im Kühlschrank sieben Portionen (26.6 Gramm) Amphetamin (MDMA). Im Zimmer von X._ entdeckte sie 48 Portionen Marihuana (insgesamt 558.7 Gramm), Verpackungsmaterial (Minigrips, Vakuummaschine), zwei Feinwagen sowie mehrere Waffen (1 Armee-Sturmgewehr mit Verschluss, 2 Pistolen, 6 Messer, 1 Elektroschockgerät) und Munition. Der Hausdurchsuchungsbefehl gegen Y._ wurde am folgenden Tag von der Staatsanwaltschaft schriftlich bestätigt und ihm ausgehändigt. B. Das Bezirksgericht Zürich verurteilte X._ am 23. August 2012 wegen Widerhandlungen gegen das Betäubungsmittelgesetz sowie Widerhandlung und Übertretung des Waffengesetzes zu einer bedingten Geldstrafe von 150 Tagessätzen zu Fr. 30.-- und einer Busse von Fr. 500.--. Im Berufungsverfahren sprach das Obergericht des Kantons Zürich X._ am 26. März 2013 vollumfänglich frei. C. Die Oberstaatsanwalt des Kantons Zürich führt Beschwerde in Strafsachen mit dem Antrag, das obergerichtliche Urteil sei aufzuheben und die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. X._ beantragt, die Beschwerde abzuweisen. Das Obergericht hat auf eine Vernehmlassung verzichtet. 