Computer Science
The number that appears once
A list holds whole numbers. Every number appears exactly twice, except one, which appears once. How do you find it, using only a fixed amount of extra memory?
- Hint 1Sorting works, but can you do it in one pass?
- Hint 2Think of an operation where x combined with x gives nothing, and the order does not matter.
- Use bitwise exclusive or (XOR): x XOR x = 0, x XOR 0 = x, and XOR is commutative and associative.
- Start with 0 and XOR in every number in the list.
- Each pair cancels to 0 whatever order they come in, so what is left is the single number.
- One pass, one variable: time grows linearly with the list, memory stays fixed.
Where it lands: XOR all the numbers together; the result is the one that appears once.
The trap: Using a running sum: it cannot tell which numbers were paired, and a dictionary of counts uses memory that grows with the list.
What a tutor might ask next: What if every number appears three times except one?
Now do one out loud. In the interview you think aloud with a tutor. Try a Computer Science problem with hints, follow-ups and Mia's feedback on how you think.