277. An array of size n + 2 contains every number 1..n once except two numbers that appear twice. Find both.
MediumSearching & selection
Technical
Show model answer
Hashing finds them in O(n) time and O(n) space. For O(1) space, XOR all elements with 1..n to get x ⊕ y, where x and y are the repeated values. Pick any set bit of that result (for example `r & -r`); x and y differ in that bit. Split both the array and 1..n by that bit and XOR each group separately: one group yields x and the other y.
A math alternative uses the sum and sum of squares to form two equations: S = x + y and P = x² + y², so (x − y)² = 2P − S², which together with S gives both values; however, the squares overflow quickly for large n. The XOR method is O(n) time, O(1) space and overflow-free. The negation trick (mark index a[i] negative) also works if modifying the array is allowed.