Finding the number missing in the sequence

Question

I have been given a list of n integers and these integers are in the range of 1 to n. There are no duplicates in list.But one of the integers is missing in the list.I have to find the missing integer.

Example: If n=8
I/P    [7,2,6,5,3,1,8]
O/P    4

I am using a simple concept to find the missing number which is to get the 
sum of numbers 
       total = n*(n+1)/2
And then Subtract all the numbers from sum.

But the above method will fail if the sum of the numbers goes beyond maximum allowed integer.

So i searched for a second solution and i found a method as follows:

 1) XOR all the elements present in arr[], let the result of XOR be R1.
 2) XOR all numbers from 1 to n, let XOR be R2.
 3) XOR of R1 and R2 gives the missing number.

How is this method working?..How is the XOR of R1 and R2 finds the missing integer in the above case?

How about brute forcing it? Sort the array, check the couple of indexes for which `[n - (n-1)]` does not equal 1. — Geeky Guy, Aug 20 '13 at 12:56
@VoronoiPotato: What if there are 1 billion numbers in the sequence and he's limited to 32-bit integers? — Jim Mischel, Aug 20 '13 at 13:04
@Renan because that's slower? And anyway the OP isn't asking for an alternative solution but about why/how the proposed one works. — harold, Aug 20 '13 at 13:05

score 34 · Accepted Answer · edited Aug 20 '13 at 13:26

To answer your question , you just have to remember that

A XOR B = C => C XOR A = B

and it immediately follows that

(PARTIAL SUM) XOR (MISSING ELEMENT) = (TOTAL) => 
(TOTAL) XOR ( PATIAL SUM) = (MISSING ELEMNT)

To prove the first property, just write down the XOR truth table:

A B | A XOR B
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

Truth table in short : if both the bits are same, result of XOR is false, true otherwise.

On an unrelated note, this property of XOR makes it a nice candidate for simple ( but not trivial ) forms of encryption.

score 4 · Answer 2 · answered Aug 20 '13 at 13:04

First of all, you can make your original method work even in the presence of integer overflow (as long as n fits in an int).

As to the XOR method, observe that R1 xor M == R2 (where M is the missing number). From this it follows that R1 xor M xor R2 == 0 and therefore M == R1 xor R2.

score 4 · Answer 3 · answered Aug 20 '13 at 13:05

The XOR works because every time you XOR a bit with 1 you flip it, and every time you XOR a bit with 0 it stays the same. So the result of XORing all the data save the missing number gives you the 'negative' impression of XORing all the numbers. XORing these two together restores your lost number.

score 1 · Answer 4 · answered Aug 20 '13 at 13:11

Let's just look at the XOR of the low order bit (LOB) to keep things simple. Let x be the missing integer.

Each integer in the list contributes a 1 or a zero the LOB of R1 (LOB(R1)).

Each integer in the range contributes a 1 or a zero to the LOB(R2).

Now suppose LOB(R1) == LOB(R2). Since R2 == R2 XOR x, this can only happen if LOB(x) == 0 == LOB(R1) XOR LOB(R2). (1 xor 1 = 0, 0 xor 0 = 0)

Or suppose (LOB(R1) == LOB(R2). This can only happen if LOB(x) == 1 == LOB(R1) XOR LOB(R2) (1 xor 0 = 1, 0 xor 1 = 1).

But what works for the low order bit works for all of them, because XOR is computed independently, bit by bit.

Finding the number missing in the sequence

4 Answers4

Linked