Missing Number

Given numbers from 1 to n with exactly one missing, find it. [1,2,4,5], n=5 → 3. (LeetCode 268)

Brute force: for each 1..n, linear-search the array — O(n²).

Hashing: mark seen numbers in a hash array of size n+1, then scan for the unmarked one.

Optimal — sum formula: the sum of 1..n is n(n+1)/2. Subtract the actual array sum from that — the difference is the missing number.

sum = n * (n + 1) / 2;
s2 = 0;
for (i = 0 -> n) s2 += arr[i];
return sum - s2;

Alternative optimal — XOR: XOR-ing a number with itself gives 0, and XOR-ing with 0 leaves it unchanged. XOR every number 1..n together with every array element together — everything that appears in both cancels out, leaving only the missing number. This can be done in one pass by XOR-ing the index and the array element simultaneously:

int xor1 = 0, xor2 = 0;
int n = arr.size();
for(int i = 0; i < n; i++){
    xor2 = xor2 ^ arr[i];
    xor1 = xor1 ^ (i + 1);
}
return xor1 ^ xor2;