Sachverhalt:
A.
In Bestätigung des Urteils des Bezirksgerichts Zürich vom 16. Dezember 2015 erklärte das Obergericht des Kantons Zürich X._ am 3. November 2016 der versuchten vorsätzlichen Tötung, der Vergewaltigung, der mehrfachen sexuellen Nötigung, der versuchten sexuellen Handlungen mit Kindern, der mehrfachen Drohung, des Exhibitionismus, der Hinderung einer Amtshandlung, der sexuellen Belästigung und der Tätlichkeiten schuldig. Unter Berücksichtigung der rechtskräftigen Schuldsprüche wegen mehrfacher einfacher Körperverletzung, mehrfachen Exhibitionismus, sexueller Belästigung und mehrfacher Übertretung des Betäubungsmittelgesetzes verurteilte es ihn zu einer Freiheitsstrafe von 101⁄2 Jahren, einer Geldstrafe von 90 Tagessätzen zu Fr. 10.-- sowie einer Busse von Fr. 1'000.--. Es ordnete keine Verwahrung an.
Hinsichtlich der Schuldsprüche der versuchten vorsätzlichen Tötung, der Vergewaltigung und der sexuellen Nötigung, begangen am 8. Oktober 2013, erachtet das Obergericht zusammengefasst folgenden Sachverhalt als erstellt:
X._ würgte eine Prostituierte in deren Hotelzimmer derart fest, dass eine unmittelbare und konkrete Lebensgefahr eintrat. In der Folge drang er gegen den Willen der Prostituierten mit seinem Glied anal und vaginal in sie ein, wobei er sie weiterhin am Hals beziehungsweise am Genick festhielt.
B.
Die Oberstaatsanwaltschaft des Kantons Zürich beantragt mit Beschwerde in Strafsachen, die Ziffern 1 al. 1 (versuchte vorsätzliche Tötung), 2 (Strafe) sowie 4 (Verwahrung) des obergerichtlichen Urteils seien aufzuheben, X._ sei des versuchten Mordes schuldig zu sprechen und zu einer Freiheitsstrafe von 141⁄2 Jahren, einer Geldstrafe von 90 Tagessätzen zu Fr. 10.-- und einer Busse von Fr. 1'000.-- zu verurteilen. Zudem sei er zu verwahren. Eventualiter seien die vorgenannten Dispositiv-Ziffern des obergerichtlichen Urteils aufzuheben und die Sache zur neuen Beurteilung an das Obergericht zurückzuweisen.
C.
Das Obergericht verzichtet auf eine Stellungnahme zur Beschwerde.
X._ lässt sich vernehmen und beantragt, (1.) auf die Beschwerde der Oberstaatsanwaltschaft sei nicht einzutreten, eventualiter sei sie vollumfänglich abzuweisen; (2.) die Frist zur Beschwerde in Strafsachen sei wiederherzustellen; (3.) Ziffer 1 al. 1 (versuchte vorsätzliche Tötung) des obergerichtlichen Urteils sei aufzuheben und das Verfahren sei im Sinne der Erwägungen (Freispruch vom Vorwurf) sowie zum Zwecke der Strafzumessung an die Vorinstanz zurückzuweisen. Schliesslich ersucht er um unentgeltliche Rechtspflege und Verbeiständung.
Im Rahmen des zweiten Schriftenwechsels verzichtet das Obergericht erneut darauf, sich vernehmen zu lassen. Die Oberstaatsanwaltschaft hält in ihrer Replik an ihren in der Beschwerde gestellten Anträgen sowie deren Begründung fest und beantragt, das Gesuch von X._ um Wiederherstellung der Frist zur Beschwerde in Strafsachen sei abzuweisen. X._ hält in seiner Duplik an seinen Anträgen fest.
Erwägungen:
1.
1.1. Der Beschwerdegegner ersucht in seiner Stellungnahme zur Beschwerde der Beschwerdeführerin darum, dass seine Frist für eine Beschwerde in Strafsachen wieder hergestellt wird. Er macht geltend, als sein damaliger Verteidiger die Beendigung des Mandats deklariert habe, habe er sich aufgrund eines psychotischen Geschehens in der psychiatrischen Klinik Rheinau befunden. In diesem Zustand sei es ihm offensichtlich unmöglich gewesen, eine Beschwerde in einer derart komplexen Angelegenheit zu verfassen. Es wäre daher an seinem damaligen Verteidiger gewesen, eine Beschwerde einzureichen, was dieser nicht getan habe. Vielmehr habe er sein Mandat mit Schreiben vom 7. November 2016 niedergelegt. Dies sei zur Unzeit erfolgt und mit den Regeln der Anwaltskunst nicht vereinbar; der Verzicht auf eine Beschwerde an das Bundesgericht erscheine zudem als grobfahrlässige Unterlassung. Dem Beschwerdegegner komme kein Verschulden zu, da er offensichtlich keinen genügenden Willen habe bilden können. Es stelle sich zudem die Frage, ob auch im bundesgerichtlichen Verfahren eine notwendige Verteidigung eingesetzt werden müsse, wenn der bisherige Anwalt das Mandat niederlege; dies zumindest für Fälle, in denen die Staatsanwaltschaft Beschwerde erhebe (Hinweis auf Art. 6 Ziff. 3 lit. c EMRK, Art. 14 Abs. 3 lit. c und d UNO-Pakt II; Urteil 6B_294/2016 vom 5. Mai 2017 E. 2.3; Urteil des EGMR Bauer gegen Deutschland vom 1. September 2016). Schliesslich weist der Beschwerdegegner darauf hin, dass sein jetziger Vertreter erst seit dem 16. Juni 2017 über die Vollzugsakten verfüge, die seinen psychotischen Zustand belegten.
1.2. Die Beschwerde gegen einen Entscheid ist innert 30 Tagen nach der Eröffnung der vollständigen Ausfertigung beim Bundesgericht einzureichen (Art. 100 Abs. 1 BGG).
Das begründete vorinstanzliche Urteil wurde dem damaligen amtlichen Verteidiger des Beschwerdegegners am 13. Dezember 2016 zugestellt beziehungsweise von einer von diesem bevollmächtigten Person am Postschalter in Empfang genommen (kantonale Akten, act. 167). Damit endete die 30-tägige Frist zur Einreichung der Beschwerde in Strafsachen unter Berücksichtigung von Art. 45 Abs. 1 und Art. 46 Abs. 1 lit. c BGG am 30. Januar 2017. Der Beschwerdegegner reichte seine Beschwerde in Strafsachen erstmals am 20. Juni 2017 ein, womit diese grundsätzlich verspätet erfolgte. Es ist daher zu prüfen, ob seinem Fristwiederherstellungsgesuch entsprochen werden kann.
1.3. Ist eine Partei oder ihr Vertreter durch einen anderen Grund als die mangelhafte Eröffnung unverschuldeterweise abgehalten worden, fristgerecht zu handeln, so wird gemäss Art. 50 Abs. 1 BGG die Frist wiederhergestellt, sofern die Partei unter Angabe des Grundes innert 30 Tagen nach Wegfall des Hindernisses darum ersucht und die versäumte Rechtshandlung nachholt. Krankheit kann nach der Rechtsprechung ein unverschuldetes Hindernis nach Art. 50 Abs. 1 BGG darstellen, sofern sie derart ist, dass sie den Rechtssuchenden davon abhält, innert Frist zu handeln oder dafür einen Vertreter beizuziehen (BGE 119 II 86 E. 2a S. 87 mit Hinweis). Die Erkrankung muss den Rechtssuchenden davon abhalten, selber innert Frist zu handeln oder eine Drittperson mit der Vornahme der Prozesshandlung zu betrauen. Dass es sich so verhält, muss mit einschlägigen Arztzeugnissen belegt werden, wobei die blosse Bestätigung eines Krankheitszustandes und regelmässig selbst einer vollständigen Arbeitsunfähigkeit zur Anerkennung eines Hindernisses im Sinne von Art. 50 Abs. 1 BGG nicht genügt (vgl. Urteile 6B_1154/2016 vom 1. November 2016 E. 2; 1C_497/2016 vom 27. Oktober 2016 E. 4.2; 6B_230/2010 vom 15. Juli 2010 E. 2.2 mit Hinweisen).
Der Beschwerdegegner belegt seinen Antrag zur Fristwiederherstellung mit dem Dokument "Einweisung zur Krisenintervention" des Psychiatrisch-Psychologischen Diensts des Amts für Justizvollzug des Kantons Zürich vom 2. Dezember 2016. Demnach wurde er wegen Verdachts auf ein psychotisches Geschehen von der Justizvollzugsanstalt Pöschwies in die Psychiatrische Klinik Rheinau verlegt. Es ist weder der Einweisung noch den Ausführungen des Beschwerdegegners zu entnehmen, ob sich der Verdacht auf ein psychotisches Geschehen schliesslich bestätigte und wie lange dieses gegebenenfalls andauerte. Damit ist bereits fraglich, ob das Gesuch um Wiederherstellung der Beschwerdefrist genügend begründet ist. Es ist nicht Aufgabe des Bundesgerichts, Nachforschungen zu einem möglichen Wiederherstellungsgrund anzustellen. Die Frage kann jedoch offen bleiben, da sich aus den bundesgerichtlichen Akten ergibt, dass der Beschwerdegegner seinen jetzigen Vertreter am 15. Mai 2017 bevollmächtigte (Datum der Vollmacht; act. 8). Unbesehen der Tatsache, dass er seinen Anwalt bereits vor diesem Zeitpunkt kontaktiert haben muss, steht fest, dass der Beschwerdegegner spätestens am 15. Mai 2017 in der Lage war, eine Drittperson mit der Wahrung seiner Interesse zu betrauen. Damit fiel ein allenfalls unverschuldetes Hindernis am 15. Mai 2017 weg, womit die 30-tägige Frist von Art. 50 Abs. 1 BGG am 16. Mai 2017 begann und am 14. Juni 2017 endete. Der Beschwerdegegner ersuchte erstmals in seiner Stellungnahme vom 20. Juni 2017 darum, die Frist zur Beschwerde in Strafsachen wieder herzustellen. Das Gesuch erfolgte damit verspätet, weshalb darauf nicht einzutreten ist. Gleiches gilt folglich für seine Beschwerde in Strafsachen.
Nicht weiter einzugehen ist auf den Hinweis des Beschwerdegegners auf sein konventionsrechtlich verbürgtes Recht auf eine wirksame Verteidigung. Dieser Anspruch führt nicht dazu, dass die 30-tägige Frist von Art. 50 Abs. 1 BGG unbeachtlich würde (vgl. zur Frage der "notwendigen" Verteidigung vor Bundesgericht: Urteil 6B_720/2015 vom 5. April 2016 E. 3.2). Am Umstand, dass das Fristwiederherstellungsgesuch verspätet erfolgte, würde auch nichts ändern, wenn der frühere Verteidiger des Beschwerdegegners verpflichtet gewesen wäre, beim Bundesgericht eine Beschwerde einzureichen. Es erübrigt sich daher, diese vom Beschwerdegegner aufgeworfene Frage zu erörtern.
2.
2.1. Die Beschwerdeführerin wendet sich gegen die Qualifikation des tätlichen Übergriffs des Beschwerdegegners als versuchte vorsätzliche Tötung und rügt eine Verletzung von Art. 112 StGB. Sie argumentiert, da gemäss Rechtsprechung und Lehre die Tötung eines Menschen zum Zwecke eines Raubes als skrupellos gelte, müsse auch die Tötung eines Menschen zur Durchsetzung des Geschlechtsverkehrs skrupellos sein. Für die Annahme der Skrupellosigkeit genüge es, dass als besonders verwerfliches Motiv das Durchsetzen des Geschlechtsverkehrs um jeden Preis und entsprechend ein krasses Missverhältnis zwischen dem vom Beschwerdegegner verfolgten Zweck sowie der in Kauf genommenen (versuchten) Auslöschung eines Menschenlebens bestanden hätten, wobei das Opfer zum blossen Objekt der Wut und Gereiztheit des Täters geworden sei.
2.2. Die Vorinstanz erachtet als erstellt, dass sich der Beschwerdegegner mit dem Opfer auf dessen Hotelzimmer begeben habe, um sexuelle Handlungen vorzunehmen. Dort sei es zwischen ihnen zu einer verbalen Auseinandersetzung hinsichtlich der Modalitäten der auszuführenden sexuellen Handlungen gekommen (Urteil S. 22). In der Folge habe der Beschwerdegegner das Opfer mit einer Hand vorne am Hals gepackt, habe es auf das Bett gestossen und es mit beiden Händen von vorn gewürgt, wobei er ihm, als es geschrien habe, damit gedroht habe, es umzubringen. Ferner habe er ihm den Zeige- und Mittelfinger in den Hals gesteckt, woraufhin es aus dem Mund geblutet habe. Alsdann habe er den Druck am Hals während einer nicht bekannten Zeit so massiv verstärkt, dass das Opfer keine Luft mehr bekommen und gedacht habe, es müsse sterben, ein "Klicken" am Hals gehört habe und ihm schwarz vor Augen geworden sei. Für kurze Zeit sei es weggetreten gewesen. In der Folge habe er das Opfer und sich ausgezogen, wobei er es zwischendurch immer wieder am Hals festgehalten habe, auf das Bett gestossen sowie erneut während einer nicht bekannten Zeitspanne gewürgt, sodass es wieder keine Luft bekommen habe. Als es versucht habe, ihn wegzustossen, habe er es mit der Faust gegen den Mund geschlagen. Im Anschluss sei der Beschwerdegegner gegen den Willen des Opfers mit seinem Glied anal und vaginal in dieses eingedrungen, wobei er es am Hals beziehungsweise am Genick festgehalten habe. Im Zeitpunkt des Würgens habe sich das Opfer in unmittelbarer und konkreter Lebensgefahr befunden (Urteil S. 9 ff., 20). Der Beschwerdegegner habe um die möglichen tödlichen Folgen beim Würgen eines Menschen gewusst. Er habe nicht darauf vertrauen dürfen, dass sein Angriff nicht tödlich, sondern glimpflich verlaufen würde. Es sei deshalb davon auszugehen, dass er den Erfolg in Kauf genommen habe (Urteil S. 20 ff., 26). Ferner habe er die Gegenwehr des Opfers gegen die sexuellen Handlungen erkannt (Urteil S. 20 ff.).
Hinsichtlich der Abgrenzung der versuchten vorsätzlichen Tötung zum versuchten Mord erwägt die Vorinstanz, zur Motivlage des Beschwerdegegners sei wenig bekannt. Es sei naheliegend, dass der Beweggrund für den Angriff das Durchsetzen des Geschlechtsverkehrs gewesen sei - mithin das Erzwingen der Erfüllung der Vereinbarung durch das Opfer; dies um jeden Preis, was als krasser Egoismus ein besonders verwerfliches Motiv darstelle. Schliesslich habe der Beschwerdegegner, als das Opfer durch das heftige Würgen nicht mehr zu einer relevanten Gegenwehr fähig gewesen sei, den Geschlechtsverkehr bis zur Ejakulation vollzogen. Sein Handeln sei von primitivem Egoismus geprägt gewesen. Zudem bestehe ein krasses Missverhältnis zwischen dem vom Beschwerdegegner verfolgten Zweck und der in Kauf genommenen (versuchten) Auslöschung eines Menschenlebens. Das Opfer sei aufgrund seiner körperlichen Unterlegenheit wehrlos gewesen und müsse grundsätzlich auch als arglos bezeichnet werden. Ausgeschlossen werden könne, dass der Beschwerdegegner bereits im Vorfeld geplant habe, das Opfer unter Ausnützung seines Vertrauens in sein Zimmer zu locken, um sich über dieses herzumachen. Zu seinen Gunsten sei anzunehmen, dass es zwischen ihm und dem Opfer zuvor zu einer Auseinandersetzung bezüglich der Modalitäten des anstehenden Geschlechtsverkehrs gekommen sei, so dass der Angriff des Beschwerdegegners nicht "aus heiterem Himmel" erfolgt sei, wie dies die Anklageschrift umschreibe. Zutreffend sei, dass der Beschwerdegegner das Opfer letztlich durch seinen tätlichen Übergriff zum blossen Objekt seiner Wut und Gereiztheit gemacht habe. Er habe ihm jedoch nicht grössere physische oder psychische Schmerzen, Leiden oder Qualen zugefügt, als sie mit einer Tötung durch Erwürgen notwendigerweise verbunden seien. Die durch den Beschwerdegegner angewandte Gewalt sei zu einem grossen Teil auch im Zusammenhang mit der folgenden Vergewaltigung sowie sexuellen Nötigung zu sehen und werde unter diesen Titeln abgegolten. Die Tatausführung an sich könne nicht als besonders verwerflich bezeichnet werden, gehe sie doch nicht über das dem Sexualdelikt immanente Mass an Verwerflichkeit und Skrupellosigkeit hinaus. Die Vorinstanz hält zusammenfassend fest, dass der Beweggrund der Tat zwar verwerflich sei und durchaus von Skrupellosigkeit zeuge. Jedoch liessen insbesondere die Tatausführung und die gesamten Umstände die besondere Skrupellosigkeit in einer Gesamtwürdigung entfallen. Die durch den Beschwerdegegner begangene versuchte Tötung sei nicht als versuchter Mord im Sinne von Art. 112 i.V.m. Art. 22 Abs. 1 StGB zu qualifizieren (Urteil S. 28 ff.).
2.3. Eine vorsätzliche Tötung ist als Mord zu qualifizieren, wenn der Täter besonders skrupellos handelt, namentlich wenn sein Beweggrund, der Zweck der Tat oder die Art der Ausführung besonders verwerflich sind (Art. 112 StGB). Mord zeichnet sich nach der Rechtsprechung durch eine aussergewöhnlich krasse Missachtung fremden Lebens bei der Durchsetzung eigener Absichten aus. Es geht um die besonders verwerfliche Auslöschung eines Menschenlebens. Für die Qualifikation verweist das Gesetz in nicht abschliessender Aufzählung auf äussere (Ausführung) und innere Merkmale (Beweggrund, Zweck). Diese müssen nicht alle erfüllt sein, um Mord anzunehmen. Entscheidend ist eine Gesamtwürdigung der äusseren und inneren Umstände der Tat. Eine besondere Skrupellosigkeit kann beispielsweise entfallen, wenn das Tatmotiv einfühlbar und nicht krass egoistisch war, so etwa wenn die Tat durch eine schwere Konfliktsituation ausgelöst wurde. Für Mord typische Fälle sind die Tötung eines Menschen zum Zwecke des Raubes, Tötungen aus religiösem oder politischem Fanatismus oder aus Geringschätzung. Die für eine Mordqualifikation konstitutiven Elemente sind jene der Tat selber, während Vorleben und Verhalten nach der Tat nur heranzuziehen sind, soweit sie tatbezogen sind (BGE 141 IV 61 E. 4.1 S. 64 f.; 127 IV 10 E. 1a S. 13 f.; Urteil 6B_480/2016 vom 5. August 2016 E. 1.3.2; je mit Hinweisen). Nach der bundesgerichtlichen Rechtsprechung und der herrschenden Lehre kann Mord auch eventualvorsätzlich begangen werden (BGE 112 IV 65 E. 3b S. 65 f.; Urteile 6B_685/2017 vom 20. September 2017 E. 2.1; 6B_832/2015 vom 25. Januar 2016 E. 1.3.1; 6B_939/2013 vom 17. Juni 2014 E. 3.1; 6B_232/2012 vom 8. März 2013 E. 1.4.2; je mit Hinweisen).
2.4. Die vorinstanzliche Gesamtwürdigung der äusseren und inneren Umstände ist bundesrechtskonform. Die Vorinstanz bezeichnet den Beweggrund des Beschwerdegegners, die Durchsetzung des Geschlechtsverkehrs, zutreffend als verwerflich und skrupellos (vgl. hierzu Urteil 6S.104/2002 vom 22. Oktober 2003 E. 2). Jedoch berücksichtigt sie in Nachachtung der bundesgerichtlichen Rechtsprechung in ihrer Gesamtwürdigung neben diesem inneren Umstand auch die äusseren Merkmale, insbesondere die Tatausführung. Hierzu äussert sich die Beschwerdeführerin in ihrer Beschwerde nicht. Es ist nicht zu beanstanden, wenn die Vorinstanz zum Schluss gelangt, die Tatausführung sei nicht besonders grausam. Dabei berücksichtigt sie zutreffend, dass der Beschwerdegegner dem Opfer nicht grössere physische oder psychische Schmerzen zufügte, als sie mit einer Tötung durch Erwürgen notwendigerweise verbunden sind. Auch kann das Vorgehen des Beschwerdegegners nicht als heimtückisch bezeichnet werden. Die Vorinstanz verletzt kein Bundesrecht, indem sie aufgrund der gesamten Umstände die besondere Skrupellosigkeit verneint und die Tat des Beschwerdegegners als versuchte vorsätzliche Tötung qualifiziert. Die Beschwerde ist in diesem Punkt unbegründet.
2.5. Ihren Antrag im Strafpunkt begründet die Beschwerdeführerin einzig mit der anderen rechtlichen Qualifikation, womit ihm keine eigenständige Bedeutung zukommt (Beschwerde S. 4). Darauf ist nicht einzutreten.
3.
3.1. Die Beschwerdeführerin rügt, die Vorinstanz verkenne die Voraussetzungen zur Anordnung einer Verwahrung gemäss Art. 64 Abs. 1 lit. a StGB. Entgegen deren Ansicht erweise sich die Anordnung der Verwahrung angesichts der Umstände als verhältnismässig und unabdingbar.
3.2. Die Vorinstanz erwägt, der Beschwerdegegner habe mit der versuchten vorsätzlichen Tötung, der Vergewaltigung und der mehrfachen sexuellen Nötigung gleich mehrere Anlasstaten im Sinne von Art. 64 Abs. 1 StGB begangen. Gemäss forensisch psychiatrischem Gutachten leide der Beschwerdegegner nicht an einer anhaltenden oder langandauernden psychischen Störung von erheblicher Schwere im Sinne von Art. 64 Abs. 1 lit. b StGB, womit es letztlich auch an den Grundlagen zur Anordnung einer Massnahme fehle. Jedoch habe der Gutachter beim Beschwerdegegner deutlich akzentuierte narzisstische und zum Teil auch antisoziale Wesenszüge festgestellt, die mit einer erhöhten Wahrscheinlichkeit für kriminelles Verhalten assoziiert seien. Die Rückfallgefahr sei sowohl für leichte bis mittelschwere als auch für schwere Gewalt- sowie Sexualstraftaten hoch. Aus dem Gutachten ergebe sich jedoch, dass das Rückfallrisiko eher "mittel bis hoch" als "sehr hoch" sei. Die Vorinstanz gelangt zum Schluss, dass die gesetzlichen Voraussetzungen zur Anordnung einer Verwahrung grundsätzlich erfüllt seien und eine Verwahrung geeignet sei, der Rückfallgefahr des Beschwerdegegners zu begegnen. Allerdings sei auch der normale Strafvollzug darauf ausgerichtet, resozialisierend und bessernd auf einen Täter zu wirken. Mit Blick auf die Verhältnismässigkeit seien hohe Anforderungen an die Annahme einer Ernsthaftigkeit der Rückfallgefahr zu stellen. Gegenüber psychisch gesunden Ersttätern, bei denen eine valide Prognose ungleich schwerer sei, dürfe die Verwahrung nur in Extremfällen ausgesprochen werden. Beim Beschwerdegegner handle es sich insoweit um einen psychisch gesunden Ersttäter, als er gemäss Gutachten keine schwere psychische Störung aufweise. Infolge seiner dissozial und narzisstisch-akzentuierten Persönlichkeit sei er zwar in einem erhöhten Mass rückfallgefährdet, müsse jedoch nicht einer Höchstrisikogruppe zugeordnet werden. Auch die Analyse der Anlasstaten lege nicht den Schluss nahe, beim Beschwerdegegner sei von einer besonders ausgeprägten Gefährlichkeit auszugehen. Zwar zeuge das Vorgehen des Beschwerdegegners beim Tötungsversuch und den folgenden Sexualdelikten von einem erheblichen Gewaltpotential sowie von massiver Geringschätzung menschlichen Lebens zur Durchsetzung eigener Interessen; diese Taten stünden jedoch alleine da. Bei den übrigen zahlreichen Delikten handle es sich um Taten im eher niederschwelligen Bereich. Beim Beschwerdegegner könne demnach nicht von einem Extremfall gesprochen werden, bei welchem sich trotz der Tatsache, dass es sich bei ihm um einen Ersttäter handle, die Anordnung der Verwahrung aufdrängen würde. In Würdigung aller Umstände erscheine die Anordnung der Verwahrung als nicht verhältnismässig (Urteil S. 71 ff.).
3.3.
3.3.1. Gemäss Art. 56 Abs. 1 StGB ist eine Massnahme anzuordnen, wenn eine Strafe allein nicht geeignet ist, der Gefahr weiterer Straftaten des Täters zu begegnen (lit. a), ein Behandlungsbedürfnis des Täters besteht oder die öffentliche Sicherheit dies erfordert (lit. b) und die Voraussetzungen der Artikel 59-61, 63 oder 64 erfüllt sind (lit. c). Die Anordnung einer Massnahme setzt voraus, dass der mit ihr verbundene Eingriff in die Persönlichkeitsrechte des Täters im Hinblick auf die Wahrscheinlichkeit und Schwere weiterer Straftaten nicht unverhältnismässig ist (Art. 56 Abs. 2 StGB).
Hat der Täter eine unter Art. 64 Abs. 1 StGB fallende Straftat verübt, so ordnet das Gericht gemäss Art. 64 Abs. 1 lit. a StGB die Verwahrung an, wenn auf Grund der Persönlichkeitsmerkmale des Täters, der Tatumstände und seiner gesamten Lebensumstände ernsthaft zu erwarten ist, dass er weitere Taten dieser Art begeht. Sind die Voraussetzungen sowohl für eine Strafe wie für eine Massnahme erfüllt, so ordnet das Gericht gemäss Art. 57 Abs. 1 StGB beide Sanktionen an. Der Vollzug der Freiheitsstrafe geht der Verwahrung voraus (Art. 64 Abs. 2 Satz 1 StGB; BGE 142 IV 56 E. 2.3.1 S. 58 f.).
3.3.2. Die Verwahrung ist "ultima ratio" (BGE 139 IV 57 E. 1.3.3 S. 61; 134 IV 121 E. 3.4.4 S. 131). Sie darf nicht angeordnet werden, wenn die bestehende Gefährlichkeit des Täters auf andere Weise behoben werden kann (BGE 134 IV 121 E. 3.4.4 S. 131, 315 E. 3.3 S. 320). Darin kommt die Subsidiarität der Verwahrung im Verhältnis zu den kurativen Massnahmen zum Ausdruck (vgl. BGE 118 IV 108 E. 2a S. 113 mit Hinweisen). Die Anordnung einer Verwahrung ist unzulässig, wenn eine Massnahme nach Art. 59 StGB Erfolg verspricht (Urteile 6B_685/2014 vom 25. September 2014 E. 2.2; 6B_497/2013 vom 13. März 2014 E. 2.3). Die Verwahrung ist überdies auch unzulässig, wenn die ausgesprochene Freiheitsstrafe - allenfalls verbunden mit einer ambulanten Massnahme - dem Sicherungsbedürfnis der Allgemeinheit zu genügen vermag (vgl. Art. 56 Abs. 1 lit. a und b StGB; Urteil 6B_8/2015 vom 14. September 2015 E. 2.2). Für den richterlichen Entscheid über die Anordnung der Verwahrung ergibt sich daraus die Notwendigkeit einer vergleichenden Wirkungsprognose. Die voraussehbaren Wirkungen der Strafverbüssung, allenfalls verbunden mit einer ambulanten Massnahme, sind mit jenen des Verwahrungsvollzugs in Relation zu setzen (vgl. BGE 107 IV 17 E. 3 S. 19 f.; Urteile 6S.31/2007 vom 30. Mai 2007 E. 6.1; 6S.258/2005 vom 24. September 2005 E. 2.3; 6S.162/2000 vom 20. Dezember 2000 E. 6b/cc; siehe auch: MARIANNE HEER, in: Basler Kommentar, Strafrecht, Bd. I, 3. Aufl. 2013, N. 30 zu Art. 56 StGB; GÜNTER STRATENWERTH, Schweizerisches Strafrecht, Allgemeiner Teil II, Strafen und Massnahmen, 2. Aufl. 2006, § 12 N. 14 ff.; PETER ALBRECHT, Die richterliche Anordnung einer Verwahrung gemäss Art. 64 nStGB - ein verantwortbares Risiko?, in: Risiko und Recht, Festgabe zum Schweizerischen Juristentag 2004, S. 575 ff., 578 f.; SCHWARZENEGGER/ HUG/JOSITSCH, Strafrecht II, Strafen und Massnahmen, 8. Aufl. 2007, § 7 S. 165 f.).
Im Vergleich zu anderen Massnahmen ist bei der Verwahrung eine "qualifizierte" Gefährlichkeit erforderlich. Sie setzt eine hohe Rückfallwahrscheinlichkeit voraus. In der Praxis wird das Gericht eine solche Gefahr bejahen, wenn es sich überhaupt nicht vorstellen kann, dass der Täter keine neuen Straftaten gleicher Art begehen wird. Eine Vermutung, eine vage Wahrscheinlichkeit, eine latente Rückfallmöglichkeit oder eine latente Gefahr genügen nicht. Das Rückfallrisiko muss Straftaten gleicher Art wie jene, die eine Verwahrung des Verurteilten voraussetzt, betreffen. Mit anderen Worten wird das Gericht bei der Vornahme seiner Prognose einzig das Risiko der Begehung schwerer Straftaten gegen die psychische, physische oder sexuelle Integrität berücksichtigen dürfen (BGE 137 IV 59 E. 6.3 S. 70 mit Hinweisen; Urteile 6B_970/2013 vom 24. Juni 2014 E. 8.3; 6B_705/2013 vom 10. Dezember 2013 E. 2.2).
Dabei ist zu bedenken, dass Gefährlichkeitsprognosen naturgemäss unsicher und schwierig sind (BGE 127 IV 1 E. 2a. S. 5). Bei psychisch gesunden Ersttätern ist die Zuverlässigkeit der Prognosen noch geringer, da frühere Delinquenz das verlässlichste Indiz für die Beurteilung der Gefährlichkeit darstellt. Entsprechend wird in der Lehre die Ansicht vertreten, dass die Verwahrung gegenüber psychisch gesunden Ersttätern nur in Extremfällen ausgesprochen werden darf (Urteile 6B_970/2013 vom 24. Juni 2014 E. 8.3; 6B_705/2013 vom 10. Dezember 2013 E. 2.2; je mit Hinweis auf HEER, a.a.O., N. 51 zu Art. 64 StGB; SCHWARZENEGGER/HUG/JOSITSCH, a.a.O., § 7 S. 189; MICHEL DUPUIS ET AL., Petit Commentaire CP, N. 11 zu Art. 64 StGB).
3.3.3. Das Gericht stützt sich bei seinem Entscheid über die Anordnung einer Massnahme nach den Art. 59-61, 63 und 64 sowie bei der Änderung der Sanktion nach Art. 65 auf eine sachverständige Begutachtung (Art. 56 Abs. 3 StGB; BGE 134 IV 315 E. 4.3.1 S. 326). Das Gutachten hat sich über sämtliche tatsächlichen Voraussetzungen der Massnahmen zu äussern. Es muss sich zur Notwendigkeit und den Erfolgsaussichten einer Behandlung des Täters, Art und Wahrscheinlichkeit weiterer möglicher Straftaten und zu den Möglichkeiten des Vollzugs der Massnahme äussern (Art. 56 Abs. 3 StGB). Es hat sich weiter über die möglichen Wirkungen der verschiedenen Sanktionen vergleichend auszulassen (vgl. BGE 118 IV 108 E. 2a S. 113; 101 IV 124 E. 3b S. 128) und dazu Stellung zu nehmen, ob und inwiefern andere sichernde Massnahmen auszuschliessen sind (vgl. BGE 100 IV 142 E. 3 S. 144 f.; zum Ganzen siehe HEER, a.a.O., N. 50 f. zu Art. 56 StGB). Das Gericht darf in Fachfragen nicht ohne triftige Gründe vom Gutachten abweichen (BGE 142 IV 49 E. 2.1.3 S. 53; 141 IV 369 E. 6.1 S. 372 f.; 138 III 193 E. 4.3.1 S. 198 f.; je mit Hinweisen).
3.4. Die Beschwerdeführerin wirft der Vorinstanz vor, sie gehe fälschlicherweise davon aus, bei psychisch gesunden Ersttätern dürfe die Verwahrung nur in Extremfällen angeordnet werden. Selbst wenn dies der Fall sein sollte, sei vorliegend von einem Extremfall auszugehen. Diese Fragen, wie auch jene, ob es sich beim Beschwerdegegner überhaupt um einen Ersttäter handelt, brauchen vorliegend nicht geprüft zu werden, da die Beschwerde aus einem anderen Grund gutzuheissen ist.
Gutachten sind im Massnahmerecht nach Art. 56 ff. StGB unabdingbar. Sie werden vom Gesetzgeber und auch vom Bundesgericht in konstanter Praxis als zwingende Entscheidgrundlage bezeichnet, sofern die Indikation einer Massnahme, sei diese therapeutisch oder sichernd, zu beurteilen ist (Urteile 6B_519/2015 vom 25. Januar 2016 E. 1.2; 6B_265/2015 vom 3. Dezember 2015 E. 4.1.1). Dies gilt sowohl im positiven (das Gericht ordnet eine Massnahme an) wie auch im negativen Sinne (das Gericht verzichtet auf eine Massnahme). Das psychiatrische Gutachten vom 23. März 2015 genügt nicht als Grundlage für die Beurteilung, ob von einer Massnahme beziehungsweise einer Verwahrung abgesehen werden kann oder eine solche anzuordnen ist. Denn es nimmt nicht explizit Stellung dazu, ob eine Verwahrung nach Art. 64 StGB notwendig ist, um den Beschwerdegegner vor weiterer Gefährdung anderer abzuhalten. Zwar spricht sich das Gutachten zu Fragen der Massnahmen nach Art. 59 und 63 StGB aus, insbesondere zur (nicht vorhandenen) schweren psychischen Störung, zur Behandelbarkeit sowie zur Legalbewährung und zur Rückfallgefahr. So diagnostiziert es beim Beschwerdegegner narzisstische und antisoziale Persönlichkeitszüge, die allerdings nicht die diagnostische Schwelle einer Persönlichkeitsstörung nach ICD-10 oder DSM-5 erreichen, weshalb die Anordnung einer Massnahme nach Art. 59 beziehungsweise 63 StGB aus psychiatrischer Sicht ausscheide. Dennoch bestehe zwischen diesen Persönlichkeitszügen, seiner Lebenssituation und seiner Delinquenzentwicklung ein komplexes Bedingungsgefüge, das im Rahmen einer deliktorientierten forensisch-psychiatrischen Behandlung angegangen werden könnte, um die hohe Gefahr erneuter (leichter bis schwerer) Gewalt- und Sexualdelikte zu senken. Die Erfolgsaussichten einer Psychotherapie seien allerdings aufgrund der fehlenden Problemeinsicht, der fehlenden Veränderungsmotivation, der geringen Introspektions- und Reflektionsfähigkeit und der Fremdsprachigkeit des Beschwerdegegners gering (kantonale Akten, act. 53 S. 77 ff.).
Zur Frage der Notwendigkeit der Verwahrung lässt sich - auch mangels entsprechender Fragestellung - aus den gutachterlichen Ausführungen jedoch nur wenig ableiten. Dass eine Verwahrung als rein sichernde Massnahme eine Möglichkeit bildet, einen Straftäter von weiteren Straftaten abzuhalten, liegt auf der Hand, sagt jedoch letztlich nichts über die Notwendigkeit für deren Anordnung im konkreten Fall aus. Wohl ist die Beurteilung der Verhältnismässigkeit eine Rechtsfrage und damit vom Gericht zu entscheiden. Für diesen Entscheid muss sich dieses aber auf eine schlüssige und klare gutachterliche Beurteilung stützen können. Diese muss sich über die möglichen Wirkungen der verschiedenen Sanktionen, vorliegend insbesondere des Strafvollzugs und der Verwahrung, vergleichend auslassen, damit das Gericht die Verhältnismässigkeit einer Verwahrung beurteilen kann (vgl. E. 3.3.2 f.). Diesen Anforderungen vermag das vorliegende Gutachten nicht zu genügen.
Demnach liegt keine rechtsgenügende Entscheidgrundlage im Sinne von Art. 56 Abs. 3 StGB vor. Die tatsächlichen Verhältnisse sind nicht genügend abgeklärt, so dass die Rechtsanwendung der Vorinstanz nicht überprüft werden kann. Das vorinstanzliche Urteil ist aufzuheben und die Sache zur Einholung eines (Ergänzungs-) Gutachtens sowie zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Diese wird in ihrem neuen Entscheid im Sinne einer vergleichenden Wirkungsprognose gegebenenfalls erneut zu prüfen haben, ob nicht schon die Verbüssung der Freiheitsstrafe von 101⁄2 Jahren ausreicht, um das Sicherheitsbedürfnis der Allgemeinheit zu befriedigen, so dass die Notwendigkeit einer Verwahrung entfallen würde. Sollte das neue oder ergänzte psychiatrische Gutachten die für die Anordnung einer therapeutischen oder sichernden Massnahme massgebenden Faktoren (psychische Störung, Rückfallgefahr, Behandlungsbedürftigkeit und Behandlungsfähigkeit) anders beurteilen als das vorliegende Gutachten, steht es der Vorinstanz frei, die Anordnung weiterer Massnahmen gemäss Art. 59-61 und 63 StGB zu prüfen. In diesem Zusammenhang ist darauf hinzuweisen, dass die Frage der rechtlichen Relevanz der medizinischen Diagnose juristischer Natur ist (vgl. Urteil 6B_993/2013 vom 17. Juli 2014 E. 4.6). Die Beurteilung, ob eine vom psychiatrischen Sachverständigen diagnostizierte psychische Störung als schwer im Sinne von Art. 59 Abs. 1 und Art. 63 Abs. 1 StGB zu qualifizieren ist, obliegt daher dem Gericht.
Bei diesem Ausgang des Verfahrens braucht nicht auf die Ausführungen des Beschwerdegegners zur Beurteilung der Rückfallgefahr durch die Gutachter und die Vorinstanz eingegangen zu werden (vgl. Stellungnahme vom 21. Juli 2017 S. 7 ff.), da die Vorinstanz ein neues oder ergänzendes Gutachten einholen muss.
4.
Auf das Fristwiederherstellungsgesuch und die Beschwerde des Beschwerdegegners ist nicht einzutreten.
Die Beschwerde der Beschwerdeführerin ist teilweise gutzuheissen, das obergerichtliche Urteil aufzuheben und die Sache zu neuer Beurteilung an die Vorinstanz zurückzuweisen. Im Übrigen ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann.
Die Parteien werden im Umfang ihres Unterliegens grundsätzlich kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 1 sowie 2 BGG). Der Beschwerdegegner ersucht um unentgeltliche Rechtspflege und Verbeiständung. Soweit er obsiegt, wird das Gesuch gegenstandslos, soweit er unterliegt, ist es gutzuheissen, da von seiner Bedürftigkeit auszugehen ist und sein Rechtsbegehren nicht aussichtslos war (Art. 64 Abs. 1 und 2 BGG). Es sind keine Gerichtskosten zu erheben (Art. 66 Abs. 4 BGG). Der Kanton Zürich hat dem Beschwerdegegner für das bundesgerichtliche Verfahren im Umfang seines Obsiegens eine angemessene Entschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG). Diese ist praxisgemäss seinem Rechtsvertreter auszurichten. Im Umfang des Unterliegens ist der Rechtsvertreter des Beschwerdegegners aus der Bundesgerichtskasse zu entschädigen (Art. 64 Abs. 2 BGG). Da die Entschädigung insgesamt auf den üblichen Pauschalbetrag von Fr. 3'000.-- festgesetzt wird, kann auf die Einholung einer Kostennote verzichtet werden.
Demnach erkennt das Bundesgericht:
1.
Auf das Fristwiederherstellungsgesuch und die Beschwerde des Beschwerdegegners wird nicht eingetreten.
2.
Die Beschwerde der Beschwerdeführerin wird teilweise gutgeheissen, das Urteil des Obergerichts des Kantons Zürich vom 3. November 2016 aufgehoben und die Sache zu neuer Beurteilung an die Vorinstanz zurückgewiesen. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
3.
Das Gesuch des Beschwerdegegners um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen, soweit es nicht gegenstandslos geworden ist.
4.
Es werden keine Kosten erhoben.
5.
Der Kanton Zürich hat dem Rechtsvertreter des Beschwerdegegners, Rechtsanwalt Dr. Diego R. Gfeller, für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 1'500.-- zu bezahlen.
6.
Rechtsanwalt Dr. Diego R. Gfeller wird eine Entschädigung von Fr. 1'500.-- aus der Bundesgerichtskasse ausgerichtet.
7.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, I. Strafkammer, schriftlich mitgeteilt.
Lausanne, 23. Januar 2018
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Andres