197. Missing Number

The numbers 0..n have a known total (n*(n+1)/2). Subtract the actual sum of nums from that total and the difference is exactly the missing number.

Walk-through

1. Let n = len(nums). The complete set 0, 1, ..., n sums to expected = n * (n + 1) / 2.
2. Compute actual = sum(nums).
3. The missing number is expected - actual, because every present number cancels out and only the missing one is left in the difference.

Worked example

nums = [3, 0, 1], so n = 3.

• expected = 3 * 4 / 2 = 6.
• actual = 3 + 0 + 1 = 4.
• Missing = 6 - 4 = 2. ✓

Alternative: XOR (no overflow)

Xor all indices 0..n together with every value in nums. Pairs cancel (x ^ x = 0) and the survivor is the missing number. This avoids the large intermediate sum entirely and is also O(n) time, O(1) space.

Complexity

• Time: O(n) — one pass to sum the array.
• Space: O(1) — a couple of accumulators.

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expected = n * (n + 1) / 2;
        int actual = 0;
        for (int num : nums) {
            actual += num;
        }
        return expected - actual;
    }
}