CODEWITHSUNDEEP
algorithmdata-structures
Aravind
Aravind

Reputation: 3199

Given n-1*n array, find missing number

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?

Upvotes: 7

Views: 1696

Answers (2)

zw324
zw324

Reputation: 27210

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.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726969

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 :-)

Upvotes: 9

Related Questions