Missing Number [Medium] — Math Sum / XOR Trick

Problem Statement

Given an array containing n distinct numbers in the range [0, n], return the one missing number.

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

Intuition

Sum: Expected sum = n*(n+1)/2, subtract actual sum.

XOR: XOR all indices [0..n] with all elements — duplicates cancel, leaving missing.

Solutions

C

int missingNumber(int* nums, int n) {
    int expected = n*(n+1)/2, actual=0;
    for (int i=0;i<n;i++) actual+=nums[i];
    return expected-actual;
}

C++

int missingNumber(vector<int>& nums) {
    int n=nums.size(), sum=n*(n+1)/2;
    for (int x:nums) sum-=x;
    return sum;
}

Java

public int missingNumber(int[] nums) {
    int n=nums.length, sum=n*(n+1)/2;
    for (int x:nums) sum-=x;
    return sum;
}

JavaScript

var missingNumber = function(nums) {
    const n=nums.length;
    return n*(n+1)/2 - nums.reduce((a,b)=>a+b,0);
};

Python

def missingNumber(nums: list[int]) -> int:
    n = len(nums)
    return n*(n+1)//2 - sum(nums)

Complexity

Time: O(n)
Space: O(1)