Missing Number

Given an integer array of size n containing distinct values in the range from 0 to n (inclusive), return the only number missing from the array within this range.

Brute Force#

For each number from 0 to n, do a full linear scan of the array to check whether it is present. The first number not found is the missing one. This is correct but painfully slow — we run a nested loop that does O(n) work for each of the n+1 candidates, resulting in O(n²) overall time.

• Two loops, to linear search every number from 0 to n

Time Complexity: O(n^2),

Space Complexity: O(1)

Better Approach#

Build a frequency map (or a boolean visited array of size n+1) in one pass, then in a second pass find the index that was never marked. This reduces the time to O(n) at the cost of O(n) extra space for the map. It is faster than brute force but uses memory proportional to n, which the optimal approaches eliminate.

• Use freq map

Time Complexity: O(n) + O(n)

Space Complexity: O(n)

Better Approach - II#

After sorting, the value at each index should equal the index itself (for a 0-to-n range). A single scan finds the first position where nums[i] != i, and that index is the missing number. Sorting avoids the hash map's extra space, but costs O(n log n) time and mutates the input array — worse on both counts compared to the optimal summation approach.

• Sort and find

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        int missing = 0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]!=missing)
                return missing;
            missing++;
        }
        return nums.size();
    }
};

Time Complexity: O(nlogn)

Space Complexity: O(n)

Optimal Approach: Summation Property#

The key insight is that the sum of 0 through n is a known closed-form formula: n*(n+1)/2. The actual array sum is missing exactly one value, so the difference sumN - sum is the missing number. A single pass computes the array sum, giving O(n) time and O(1) space — a significant improvement over all previous approaches.

• Find sum of first n numbers: SumN = (n)*(n-1)/2
• Find sum of given array: Sum
• Missing = SumN - sum

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int sumN = n * (n+1)/2;

        int sum = 0;
        for(int i=0;i<n;i++){
            sum += nums[i];
        }

        return sumN - sum;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)

Optimal Approach: XOR#

XOR is self-inverse: any value XOR'd with itself cancels out to zero. We XOR together all numbers from 1 to n and all elements of the array; every present value appears twice and cancels, leaving only the missing number. This avoids the integer overflow risk that large summations can cause and still runs in O(n) time with O(1) space.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int xorR = 0;

        for(int i=0;i<nums.size();i++){
            xorR ^= (i+1);
            xorR ^= nums[i];
        }

        return xorR;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)