[jonathanlydall]

This was a go to interview question to be solved in C# at a place I worked at a while back which had developers allocated to projects working on pretty standard line of business systems.

The XOR solution was a valid answer, but not the only answer we would have happily accepted.

The interview question was chosen such that it's very easy to understand and quick to solve, meaning it would indicate the candidate knew at least the basics of programming in C#. Almost surprisingly, we actually had candidates applying for "senior" level positions who struggled with this.

It could be solved in a multitude of ways, e.g:

- XOR as above

- Use of a HashSet<int>

- Use for loop and List which contains a number and its count.

- Use LINQ to group the numbers or something and then find the one with the count.

As long as what they did worked, it was a "valid" answer, we could then often discuss the chosen solution with the candidate and see how they reacted when we let them know of other valid solutions.

It was really great for not being a "one clever trick" question and could act as a springboard to slightly deeper discussions into their technical thought processes and understanding.

[dahcryn]

you are missing the most obvious one, no? Sum both lists and take the difference, that's the missing number, since the items are guaranteed unique

[vbezhenar]

It is interesting for me to remember my very first programming task. The very first day I was introduced to programming with Pascal (I think I was 14), I was taught variables, assignments, arithmetic and was given a task to switch two variables (swap). I quickly solved it using third variable, but then I was asked to do it without third variable. It was very hard task for me, I spent few hours at home tackling it, but finally I solved it with a trick conceptually similar to XOR:

    a := a + b;
    b := a - b;
    a := a - b;

I'm still proud of little me and I always remember this solution when I encounter XOR tricks. I didn't knew about bitwise arithmetic at that time, but sometimes simple `+` can work just as well.

[zeroq]

overflow

[criddell]

Would a BigInteger sum still overflow?

[Arnavion]

It doesn't matter. Overflow is a non-issue as long as you have wrapping addition and subtraction operators, which C# does - regular `+` and `-` not inside `checked {}`. You don't need to reach for BigInteger.

[TacticalCoder]

> "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]

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]

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

[cluckindan]

You are given a magnetic tape containing a list of n - 1 integers… :-)

[jonathanlydall]

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.