1263. One Value Repeated and One Gone, With No Extra Table

An array of n values should hold every integer from 1 to n exactly once. In fact one value appears twice and one is absent. Print the repeated value, then the absent one, separated by a space.

1 2 2 4 -> 2 3 3 1 3 4 5 -> 3 2 5 5 1 2 3 -> 5 4

## What most people try first

A counting array indexed by value, which is what #290 does, and #290 is right to: when the keys are small consecutive integers, an array IS the fastest possible hash table. #59 solves the single-missing version the same way.

This problem asks for the answer in O(1) extra space instead, with the input read once and never stored. That is the version asked when the interviewer says "now do it without the array", and it is a genuinely different technique rather than the same one tuned.

## XOR gives you both answers, mixed together

XOR everything in the array, then XOR in every integer from 1 to n:

x = (a[0] ^ ... ^ a[n-1]) ^ (1 ^ 2 ^ ... ^ n)

Each value that behaves correctly appears once in each half and cancels. The repeated value R appears twice on the left and once on the right, leaving one copy. The absent value M appears zero times on the left and once on the right, leaving one copy. So

x = R ^ M

and x is not zero, because R != M and XOR is zero only for equal operands. One number holding two answers is no use yet, which is the real problem.

## Split the universe on one bit

Since x != 0 it has a lowest set bit, b = x & -x. At that position R and M DISAGREE, because that is what a set bit in their XOR means. So sort every number into two buckets by whether it has bit b, and R and M land in different buckets, whichever way round.

Now XOR each bucket separately, taking the array and 1..n together as before. Within a bucket, every well-behaved value still cancels, because both of its copies share the same bit b and so go to the same bucket. What is left in one bucket is R alone and in the other M alone.

This is the move that matters, and it is the same one #1264 uses to separate two unpaired values. A single XOR can only ever isolate ONE survivor; a bit on which two survivors differ is what lets you run two independent XORs and get one each.

## Deciding which is which

The two buckets hand you R and M with no label. Scan the array once more and count how many times the first candidate occurs: twice means it is the repeat, zero means it is the absentee. Checking for 2 and checking for 0 are equally good; what is not good is guessing from magnitude, since R can be larger or smaller than M.

## Cost

Three passes, O(n) time, and O(1) extra space: a handful of integers and no array of size n at all. #290's version is also O(n) time but O(n) space.

## Width

n is at most 200000, so every value is below 2^18 and every XOR of such values is below 2^18. The whole computation fits in a signed 32-bit integer, whose limit is 2147483647, with four orders of magnitude to spare, and JavaScript's ^ on plain Numbers is safe for exactly that reason. Nothing here needs 64 bits and nothing here needs BigInt; saying so is part of the answer, because reaching for a wider type by reflex is how the real width question stops being asked.

Constraints - `2 ≤ n ≤ 200000` - `1 ≤ a[i] ≤ n` - exactly one value appears twice and exactly one value is absent