Missing Number — XOR and Gauss Sum Two Solutions [Meta, Amazon Easy]

Problem Statement

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

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

Solution 1 — Gauss Formula
Solution 2 — XOR
C Solution
C++ Solution
Java Solution
JavaScript Solution
Python Solution
Complexity: O(n) time, O(1) space

Solution 1 — Gauss Formula

Sum from 0 to n = n*(n+1)/2. Subtract actual sum. Difference = missing number.

Solution 2 — XOR

XOR all indices 0..n together with all elements. Paired elements cancel. Missing index remains.

result = n
for i, num in enumerate(nums):
    result ^= i ^ num
return result

C Solution

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

C++ Solution

#include <vector>
#include <numeric>
using namespace std;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int expected = n * (n + 1) / 2;
        int actual = accumulate(nums.begin(), nums.end(), 0);
        return expected - actual;
    }
};

Java Solution

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;
    }
}

JavaScript Solution

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

Python Solution

from typing import List

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        return n * (n + 1) // 2 - sum(nums)
        # XOR: return reduce(xor, range(n+1)) ^ reduce(xor, nums)

Complexity: O(n) time, O(1) space

Overflow Note: For large n, use long in Java/C++. Python handles arbitrary integers natively.