No, breaking the algorithm by increasing n (the amount of numbers) makes this 100% not working in constant space.
To the question nobody asked:
You could easily modify the algorithm to get the space to be constant. (Only the solution given in the interview has this problem. The "best" solution does not have this problem.)
Basically the size of the sum should not be a problem either. Assuming that each number can be stored in constant space of b bits you could easily modify the algorithm to use less space by doing this:
- calculating the sum for each list/array mod $2^b$ ($r_1$ and $r_2$, with $r_1 ≥ r_2$)
- if $r_1 = r_2$ -> either the result is $0$ or the input is broken
- getting the difference ($d = r_1 - r_2$)
Thanks to a possible overflow caused by the number missing:
- calculate the inverted result $d' = 2^b - d = r_2 - r_1 + 2^b$ (mod $2^b$)
- search for both numbers $d$ and $d'$ in both lists - the one found exactly once is the result
If space was limited (for any reason) this would be an option.
It comes at a price: looping again over the input - which might not be possible if the data comes from a server and you do not have the storage to save it.
So almost constant space that only scales with size of the input - I would ignore it in this case because the size of numbers is often ignored. (-> 2 ints and 2 bools).
For doubling the steps in the loops. (And 2*O(n) = O(n).)
- b = 3 -> mod 8
- list1 = 3,5,7 -> 15 (mod 8) = 7
- list2 = 3,5 -> 8 (mod 8) = 0
- d = 7 - 0 = 7
- d' = 0 - 7 + 8 = 1
- b = 3 -> mod 8
- list1 = 1,3,5,7 = 16 (mod 8) = 0
- list2 = 1,3,5 = 9 (mod 8) = 1
- d = 1 - 0 = 1
- d' = 0 - 1 + 8 = 7
For both: So either 7 or 1 should be exactly once in the 2 lists.
Here 7 is both times the result and the 1 can be found only in amounts that are even.
(Writing a function to flip a bit when you find a given number while looping over those 2 lists should be easy.)
By using the length of the 2 arrays and comparing them you could easily get some information about which value ($d$ or $d'$) is not important. Calculate sum(longer array) - sum(shorter array) and you will have the number.
-> Single loop over both "arrays" in parallel and $2$ numbers of space would be the best case scenario. (And this would even work with some data stream that can't be repeated for some reason.)
In case you cannot use both arrays in parallel you would need one extra number ($≥2$ bits). Then you would add $1$ for each number in array1 and substract $1$ for each number in array2. The result is either $1$ or $-1$ which gives you information which list is longer. (Other results: something is wrong.)
As spitemaster suggested:
Using XOR can be used to improve this even more.
His idea reduces the amount of work a bit on older machines (or slower machines you can buy today - like µC) and allows you to save about 50% of the RAM (or 66% of the registers) needed above.
(If you implement the algorithm in hardware this would be really interesting, because XOR is much smaller/faster than an adder.)
The algorithm would simply run over both arrays using XOR on all values. The result is a mix of all numbers that appear 1 + 2*k times. So if there is only one such number you have the number.