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?
Subtract the sum of the numbers in the array from the sum of the n numbers. Using XOR operation − Another way to find the missing number is using XOR. Find the XOR of all the numbers up ton.
Print the missing number as a sum. 1 Create a variable sum = 1 to which will store the missing number and a counter c = 2. 2 Traverse the array from start to end. 3 Update the value of sum as sum = sum – array [i] + c and update c as c++. 4 Print the missing number as a sum.
We know that the sum of the first n natural numbers can be computed using the formula 1 + 2 + … + n = n× (n+1)/2. We can use this formula to find the missing number.
So the sum of all n elements, i.e sum of numbers from 1 to n can be calculated using the formula n* (n+1)/2. Now find the sum of all the elements in the array and subtract it from the sum of first n natural numbers, it will be the value of the missing element.
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: XOR
ing a number with itself always results in zero. The algorithm above XOR
s 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 :-)
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With