Find the id that appears once among triples

Question

A gateway now logs every order message three times (send, ack, echo), so each id should appear exactly three times. One id appears only once because two of its copies were dropped. Find the lone id in O(n) time and O(1) space. Assume non-negative ids.

Accepted Answer

Plain XOR is the wrong self-cancelling operation here: it works modulo 2, but ids repeat three times, so you want cancellation modulo 3. Look at each bit position independently. For a given bit, every id that appears three times contributes either 0 or 3 to the count of 1s in that column, both multiples of 3. So count % 3 isolates exactly the bit contributed by the lone id. Rebuild the singleton bit by bit. Tracing [2, 2, 3, 2] (binary: 10, 10, 11, 10): bit 0 has ones only from the 3, count 1, and 1 \bmod 3 = 1, so set bit 0. Bit 1 has ones from all four values, count 4, and 4 \bmod 3 = 1, so…

Find the id that appears once among triples

Your answer

More Coding questions