7

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?

Improve this question
3
  • 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)) Commented Jul 12, 2013 at 15:30
  • @Fabinout: No they are not sorted. Commented Jul 12, 2013 at 15:30
  • 1
    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. Commented Jul 12, 2013 at 15:37

2 Answers 2

Reset to default
9

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

Improve this answer
Sign up to request clarification or add additional context in comments.

14 Comments

:Interviewer meant the step where I get the sum of first N numbers, which I would get as (N*(N+1))/2, which would be in base 10, and I will have to convert it to base 2.
@Aravind the binary multiplication is quite easy.
@Aravind Multiplying in binary is not that hard either. Anyway, unless the interviewer was looking for you to know this specific trick (which would be rather silly of him, because it borders on uselessness) he should have accepted your approach as reasonable.
Is there a way to calculate the xor-sum of all numbers in the 0..N range directly like there is to calculate the arithmetic sum using (N*(N+1))/2?
Of course, here it is! Are you surprised to find it on Stack Overflow?
|
1

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.

Improve this answer

3 Comments

Both the answers are great, but I can accept only one.I have +1-ed yours.Sorry that I couldn't accept yours.Thanks! :)
@Aravind No problem, dasblinkenlight is faster than I am - in fact, his first upvote is mine, but I believe I've edited this to be different enough so I did not delete my post. You are right that you should accept his answer:)
Could you elaborate on how I can use + and - to find the missing element?Let's say for this example, 001 011 010(We are missing 4).How do we use + and - to find that?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.