The following puzzle was given to me by a friend who claimed it was given in a Google interview. If you can confirm or debunk this claim just post a comment – until then I am sure the headline will generate some traffic 🙂 .
The original question as it was given to me was:
Given an array with 2n+1 integer elements, n elements appear twice in arbitrary places in the array and a single integer appears only once somewhere inside. Find the lonely integer with O(n) operations and O(1) extra memory.
Now let’s transform this to a more digital-design-like problem. Given an SRAM of depth N and some arbitrary width K, which is filled with 2n+1 non zero values (for completeness – the rest of the 2^N – (2n+1) are all zeroes). n elements appear twice – in different places in the SRAM, while a single value appears only once.
Design a circuit with the minimum amount of hardware to find the value which appears only once.