Finding 2 Missing Numbers

Computer Science Level 3

Suppose that out of the integers from 1 to $n$ inclusive, you are given $n-2$ of them.

To identify which are the two missing numbers, Chris proposed the following solution :

Let the two numbers be $x$ and $y$ .

The value of $x+y$ can be found by taking the sum of the first $n$ numbers and subtract by the sum of the $n-2$ given numbers.

The value of $x\oplus y$ can be found by taking the xor of the first $n$ numbers and xor it with the xor of the $n-2$ given numbers.

Solve the system of equation, then we can find the two missing numbers.

The solution is actually wrong. Which of the following cases can disprove Chris' solution?

n = 7, x = 1, y = 3

n = 4, x = 1, y = 3

n = 5, x = 2, y = 3

n = 8, x = 7, y = 1

n = 8, x = 4, y = 4

n = 6, x = 1, y = 5

n = 6, x = 3, y = 5

1 solution

Agnishom Chattopadhyay
Jul 19, 2016

Chris's solution is wrong because the two equations he gets does not uniquely determine $x$ and $y$ .

For example, when $x = 7; \, y = 1; \, n = 8$ , We have $x \oplus y = 6 \\ x+y = 8$

However, when $x = 5, y = 3$ , the same conditions are met.

There is no way to distinguish between these two.

On the other hand, the case $n=6,x=3,y=5$ can be uniquely determined because the other solution $x=7,y=1$ one of them exceeds $n=6$ . Hence Chris still can use his solution.

Christopher Boo - 4 years, 11 months ago

True. Didn't notice that.

Agnishom Chattopadhyay - 4 years, 11 months ago

Finding 2 Missing Numbers

1 solution

0 pending reports