Missing Number

Problem

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

Constraints

• 1 ≤ n ≤ 10⁴
• 0 ≤ nums[i] ≤ n
• all numbers distinct

Approach — Core Patterns

This is a Core Patterns problem. The idea: pick the data structure best matched to the constraints and solve it in one clean pass. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: see the walkthrough below.

Solution code

Python

class Solution:
    def missingNumber(self, nums):
        n = len(nums)
        return n * (n + 1) // 2 - sum(nums)

Java

class Solution {
    public int missingNumber(int[] nums) {
        // XOR everything in [0..n] against everything in the array —
        // pairs cancel out (a ^ a = 0), only the missing value survives.
        int x = nums.length;             // start with n itself
        for (int i = 0; i < nums.length; i++) {
            x ^= i ^ nums[i];
        }
        return x;

        // Math alternative: expected sum n(n+1)/2 minus the actual sum.
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.