Find the injected order id with XOR

Question

A risk monitor keeps two logs of order ids. Log b is supposed to be a reshuffled copy of log a, but a rogue process injected exactly one extra order, so b contains every id in a (same multiplicities) plus one additional id.

a = [5, 2, 9]
b = [2, 9, 5, 7]        # same ids as a, plus 7
-> 7

Find the injected id in $O(n)$ time and $O(1)$ space. A frequency map works but costs $O(n)$ memory; use the bit trick.

Accepted Answer

XOR is associative, commutative, and self-cancelling: x \oplus x = 0 and x \oplus 0 = x. Every id that appears in both logs appears an even number of times overall, so it cancels to 0. The one injected id appears an odd number of times (once), so it survives. XOR everything from both logs together. Tracing the example: 5 ^ 2 ^ 9 ^ 2 ^ 9 ^ 5 ^ 7. Regroup the matched pairs: (5^5) ^ (2^2) ^ (9^9) ^ 7 = 0 ^ 0 ^ 0 ^ 7 = 7. Time O(n), space O(1). This works even if a has duplicates, since each still appears an even number of times across the two logs; it only relies on the extra id being the lone o…

Find the injected order id with XOR

Your answer

More Coding questions