> "You are given an array A of n - 1 integers"

It's an array of integers so it fits in memory (otherwise it wouldn't be called an array). As it fits in memory, n cannot be that big. I'd still ask for more requirements, TopCoder problem style: I want to know how big n can be that the array fits in memory.

I didn't know that XOR trick. My solution would be a bit arrays with n bits and two for loops: one to light each bit corresponding to a number and one for loop to find the missing number.

And if my bit array doesn't fit in memory, then neither does the array from the problem (and certainly not the HashSet etc.).

▲

williamdclt a day ago | parent | next [-]

You could make the problem harder with "you are given a stream of n - 1 integers". N could then be any number, unbound by available memory.

That makes the problem harder which makes it more interesting, a lot of the solutions wouldn't work anymore (this isn't necessarily a good interview question though)

▲

Arnavion a day ago | parent [-]

Even with the original formulation, the array doesn't have to fit in available memory. mmap exists.

	▲	cluckindan a day ago \| parent [-]
		You are given a magnetic tape containing a list of n - 1 integers… :-)

▲

jonathanlydall a day ago | parent | prev [-]

In our case we gave the list of numbers for the input which was around a dozen so memory was not a concern, again keeping the problem pretty simple.