Search for missing integer, given 4 billion unsorted integers

Question

I came across these interview questions and I was trying to figure out how to approach this problem. I read this question about SO. I understood the author’s approach, but I don’t understand the approach suggested in the accepted answer. So I went to this blog . According to this blog, we can calculate the number of zeros and ones in each of the bit positions, and from this we can find out the missing number. But then for this file there should be 2 ^ 32-1 numbers that exceed 4 billion. So this method should not work correctly? I am sure that in my understanding something is wrong, but I just can not understand the missing link.

Answer 1

If you had a "complete" sequence of numbers from 0 to 2 ^ N-1, then the number of bits set at each bit position would be equal to (and equal to (2 ^ N) / 2).

If only one number is missing, then 1 bit corresponds to bit positions that are short of one bit.

Note that this only works for grades 2, but perhaps you can develop more complex formulas for "odd" counts.

Answer 2

• add intergers up using long
• subtract the result from (N + 1) * (N + 2) / 2, where N is the number of integers in your file. The result is a missing number.

Example:

• contains 1.3
• sum = 4
• N = 2, therefore (N + 1) (N + 2) / 2 = (2 + 1) (2 + 2) / 2 = 6
• 6-sum = 6-4 = 2
• 2 - your missing number