[/dsa/leetcode]

268 - Missing Number

Wednesday, 16 September 2026

<easy> [problem]

Cyclic sort to put every value at its own index, then the two closed forms - XOR pairing and the Gauss sum - that skip the sorting entirely.

{array}{bit manipulation}{math}

Problem

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Input: nums = [3,0,1]
Output: 2

Input: nums = [0,1]
Output: 2

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8

Constraints:

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique

Follow-up: could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Approach

n slots holding n of the n + 1 values in [0, n]. Sorting and scanning for the gap is O(n log n), and a seen-array is O(n) space; the follow-up rules both out. Three ways to do better, the first general and the other two specific to the arithmetic of this particular setup.

Cyclic Sort

When the values are the valid indices, the array can sort itself: send each value to the slot matching it, so nums[v] == v for everything present. Whatever slot is left holding the wrong thing identifies the gap. See the cyclic sort note.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        const int n = nums.size();
        int i = 0;
        while (i < n) {
            int correct = nums[i];
            if (correct < n && i != correct) {
                swap(nums[i], nums[correct]);
            } else {
                i++;
            }
        }

        for (int j = 0; j < n; j++)
            if (nums[j] != j) return j;
        return n;
    }
};
nums = [3, 0, 1], n = 3
i=0  correct=3   3 == n, no home    -> i=1
i=1  correct=0   swap(1, 0)         -> [0, 3, 1]
i=1  correct=3   no home            -> i=2
i=2  correct=1   swap(2, 1)         -> [0, 1, 3]
i=2  correct=3   no home            -> i=3, stop

scan: nums[0]=0 ok, nums[1]=1 ok, nums[2]=3 != 2  ->  return 2

The final return n covers the case where nothing is out of place, meaning 0..n-1 were all present and n itself is the missing one.

  • time: O(n) — amortized, by the argument above
  • space: O(1) — but it rewrites the input, which the problem allows and the two below don’t need

XOR

Every number in [0, n] shows up twice across the indices and the values, once as an index, once as an element except the missing one, which appears only as an index. XOR annihilates pairs, so folding everything together leaves exactly the survivor.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        const int n = nums.size();
        int res = n;
        for (int i = 0; i < n; i++) res ^= i ^ nums[i];
        return res;
    }
};
nums = [3, 0, 1]
res = 3 ^ (0^3) ^ (1^0) ^ (2^1)
    = (0^0) ^ (1^1) ^ (3^3) ^ 2
    = 2
  • time: O(n) — one pass
  • space: O(1), and the input is untouched

Gauss Sum

The same cancellation done with + and -: the sum of 0..n minus the actual total is whatever went missing.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        const int n = nums.size();
        int sum = n * (n + 1) / 2;
        for (int x : nums) sum -= x;
        return sum;
    }
};
  • time: O(n)
  • space: O(1), input untouched
quantinium © 2026