Given n-1*n array, find missing number

6
votes

Here each row contains a bit representation of a number.These numbers come from 1..N Exactly one number is missing.Find the bit representation of the missing number.
The interviewer asked me this question.
I said: "We can find the sum of the given numbers and subtract it from the sum of first n numbers(which we know as (N*(N+1))/2)"
He said that involves changing from base 10 to base 2.
Can you give me a hint on how I can solve it without changing bases?

2
algorithmdata-structures
Are the numbers sorted in the first place? If not, my guess would be to generate numbers from 1..N in a bit code and check if they're in the array. I found something interesting, when you divide by 2 an even binary number (such as 12(10) : 1100(2), you just have to move the digits by one to the right (12(10)/2 : 0110(2)) – Fabinout
@Fabinout: No they are not sorted. – Aravind
Your idea was actually quite great. You can easily multiply two binary numbers, then slide the digits to the right to get the sum of the numbers in the array. Then substract the sum of numbers from the array to get the final binary missing number. – Fabinout

2 Answers

9
votes

You can XOR together all numbers from 0..N range, then XOR the numbers from the array. The result will be the missing number.

Explanation: XORing a number with itself always results in zero. The algorithm above XORs each number exactly twice, except for the missing one. The missing number will be XOR-ed with zero exactly once, so the result is going to equal the missing number.

Note: the interviewer is wrong on needing to convert bases in order to do addition: adding binary numbers is easy and fun - in fact, computers do it all the time :-)

1
votes

You can just XOR these numbers together, and XOR with 1..n. The fact that the numbers are stored in binary is a good hint, BTW.

In fact, any commutative operator with a inverse should work, since if the operator is commutative, the order does not matter, so it can be applied to the numbers you have and 1..n, with the difference being the first one is not operated on the number that is not in the array. Then you can use its inverse to find that number, with the two results you have. SO + and -, * and /, XOR and XOR and any other operators that meets the requirement all should work here.