One id duplicated, one missing, find both

Question

A settlement batch should contain every id from $1$ to $n$ exactly once. Because of a bug, one id got written twice and, as a result, a different id is entirely missing. The array still has length $n$ .

ids = [1, 2, 2, 4]      # range is 1..4: id 2 is duplicated, id 3 is missing
-> (2, 3)               # (duplicated, missing)

Return the duplicated id and the missing id in $O(n)$ time and $O(1)$ space.

Accepted Answer

XOR every array value against every number in 1..n. Each correct id cancels; the duplicate contributes an extra copy and the missing one contributes zero copies, so the accumulator ends at dup XOR missing, which is nonzero. Any bit set in that result is a bit where dup and missing differ. Pick the lowest such bit with x & -x and partition both the array and the range by it: dup and missing fall into different groups, while every fully-paired id stays within one group and cancels. XOR each group to recover one candidate; the other is candidate XOR (dup^missing). Finally, count which candidate …

One id duplicated, one missing, find both

Your answer

More Coding questions