Missing Number

Problem Overview

Given an array containing n distinct numbers taken from the range 0 to n, find the one number in that range that's missing from the array.

Why solve this?

The array's own indices secretly encode the answer here — this is the first problem in the course where index and value are two views of the same information, an idea Find All Duplicates and Find the Duplicate Number both build on later.

Pattern Recognition

When a problem guarantees values fall inside a known range tied to the array's length (like 0..n or 1..n), think about what the array would look like if every index held its correct value — the mismatch is usually the answer.

Prerequisites

• Contains Duplicate — same 'have I seen this' instinct, applied to what's absent instead of what's repeated.

Hints

1. A hash set works, but there's a way to do this with O(1) extra space.
2. The numbers 0..n sum to a known closed-form total — compare that expected sum to the array's actual sum.
3. XOR-ing every index and every value together also works, and sidesteps any integer-overflow worry entirely.

Approach

Since nums holds n distinct values drawn from the (n+1)-value range [0, n], exactly one value from that range is missing. Compute the expected sum of 0..n using the closed-form formula n*(n+1)/2, subtract the array's actual sum, and the difference is the missing number. An XOR-based version avoids any risk of integer overflow on very large inputs by XOR-ing every index 0..n together with every array value — every present value cancels with its index pairing, leaving only the missing number.

Code

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy