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 a day ago | parent | next [-]

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 a day ago | parent | next [-]

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.

▲ a day ago | parent | prev | next [-]

[deleted]

▲ zeroq a day ago | parent | prev [-]

overflow

▲

criddell a day ago | parent [-]

Would a BigInteger sum still overflow?

	▲	Arnavion a day ago \| parent [-]
		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.

▲ 2 days ago | parent | prev | next [-]

[deleted]

▲ TacticalCoder a day ago | parent | prev [-]

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