Mi a legjobb nagy O komplexitás amivel megcsinálható ez a feladat?

"Jól gondolom hogy ha O(n) időben akarom megcsinálni, akkor O(n) hely kell hozzá, ha pedig O(1) hellyel akkor O(n^2) idő?"

Nem, O(1) space-ben van O(nlogn) és O(n) megoldás is. Bár utóbbi valszeg lassabb egy O(n)/O(n)-nél a konstans faktor miatt.

Egyébként egy O(n)/O(1)-es algoritmus az, hogy összexor-olod a tömbben lévő számokat és 1-(x-1)-ig a számokat. A két érték pont a dpula számmal fog eltérni, mert azok "kioltják" egymást.

Pl C#-ban:

            var tomb = new[] {1, 4, 2, 3, 4};

            int x = 0;

            int y = 0;

            for (int i = 0; i < tomb.Length; i++)

            {

                x ^= i;

                y ^= tomb[i];

            }

            Console.WriteLine(x^y);