Find The One

Computer Science Level 1

Is it possible to design an algorithm that uses constant space for the following function?

Input: $2n + 1$ non-negative integers; every integer appears twice, except one that appears only once.

Output: The integer that appears exactly once.

Details and Assumptions: Assume that storing each integer takes constant amount of space regardless of the number of bits in the integer.

Yes No

2 solutions

Agnishom Chattopadhyay
Oct 6, 2016

The solution to this problem relies on the properties of $\oplus$ (XOR).

We know that $\oplus$ gives a zero whenever both operands are equal. $a \oplus a = 0$

Also, $0$ is the identity of the $\oplus$ . So, $a \oplus 0 = 0 \oplus a = a$

Now, suppose the integers given to us are $x_1, x_2 \cdots x_n$ . Now, because $\oplus$ is commutative, we can assume, without loss of generality, that $x_n$ is the unique integer and $x_1 = x_2, x_3 = x_4, x_5 = x_6, \cdots$ .

Then, we are assured that $x_1 \oplus x_2 \oplus x_3 \cdots x_n = x_n$

So, we can just use an accumulator to $\oplus$ all the values that are fed in:

acc = 0
for i = 1 to length(list):
   input element
   acc = acc ^ element
return acc

Look, your algorithm stores the list, instant O(n) space.

the rest of the proof... You need to relearn how to prove algorithmic complexity man... "WLOG" can be used for correctness, not complexity.

Easy example: list = (2, 1, 2) Absolutely everything in your proof breaks down.

Derek Modzelewski - 4 years, 8 months ago

That was a little rude, but I hope you understand that this supposed to be something like an online algorithm. I edited the solution for clarity.

Agnishom Chattopadhyay - 4 years, 8 months ago

Then you absolutely can't assume the order you get the elements... 'a (xor) b' isn't even defined for a,b /= 0

I may have been rude, but your solution is still fundamentally incorrect.

Derek Modzelewski - 4 years, 8 months ago

@Derek Modzelewski –

Then you absolutely can't assume the order you get the elements... 'a (xor) b' isn't even defined for a,b /= 0

It doesn't matter what the order of the elements are, right?

Agnishom Chattopadhyay - 4 years, 8 months ago

@Agnishom Chattopadhyay – If you don't define 'a (xor) b', you can't stipulate commutativity. However, instead of the set operation 'xor' you should've just used bitwise xor, included a short explanation that bits can be dealt with independently (and so all inputs to xor are 0 or 1), then you can claim commutativity and the rest of your argument follows. Since you use bitwise xor in your code, your code is correct.

Sorry I got confused by your invalid use of xor, disregard all my previous comments.

Derek Modzelewski - 4 years, 8 months ago

Ishan Sheth
Nov 10, 2016

just keep doing xor operation of all the 2n+1 numbers

Find The One

2 solutions

0 pending reports