Missing Number

EASY✓ CHIP-TIMEDLC #268 — FULL STATEMENT ↗

The drill: An array holding n distinct numbers pulled from the range 0 to n has exactly one value missing — find it without ever fully sorting the array.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array shows up holding n distinct integers, each one pulled from the range 0 through n inclusive — since that range actually has n + 1 possible values, exactly one of them never made it in.

The task is to name that missing value. Nothing about the array's order is meaningful — the values can appear in any arrangement, and no duplicates ever show up.

Only one number is ever absent, and the array's length always matches n, so the missing value can be pinned down without needing a full sort or a separate presence array.

EX 01

nums = [3, 0, 1]

→ 2

MISSING VALUE IN THE MIDDLE

EX 02

nums = [0, 1]

→ 2

MISSING THE LARGEST VALUE

EX 03

nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]

→ 8

LARGER RANGE, MISSING NEAR THE TOP

the array holds exactly n distinct integers, sized from empty up to a few hundred thousand
every value lies between 0 and n inclusive, with exactly one value absent
no duplicates ever appear in the input array
the order of the array carries no guarantee and is not meaningful

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Checking, for every candidate in the range, whether it shows up anywhere in the array works — but each check re-scans the whole thing.

HINT 2 THE STRUCTURE

Every number from 0 to n should appear exactly once except the missing one. What operation cancels a value against its own index for free?

HINT 3 ONE STEP FROM THE ANSWER

XOR every index 0..n together with every array value. Every present number cancels against the index that would have held it, leaving the missing one.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE XOR GAPPATTERN · XOR INDEX AGAINST VALUEnums = [3, 0, 1]

RUNNING XOR (n folded in)

result → 3

STEP 1

n=3, so start the accumulator at 3 — XOR in every index and every array value, and whatever survives unpaired is the missing number.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/missing-number.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        result = len(nums)
        for i, v in enumerate(nums):
            result ^= i ^ v
        return result

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 6 LN

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        for candidate in range(n + 1):
            if candidate not in nums:  # O(n) scan every time
                return candidate
        return -1

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 7 LN

class Solution {
    public int missingNumber(int[] nums) {
        int result = nums.length;
        for (int i = 0; i < nums.length; i++) {
            result ^= i ^ nums[i];
        }
        return result;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 9 LN

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        for (int candidate = 0; candidate <= n; candidate++) {
            boolean found = false;
            for (int v : nums) {
                if (v == candidate) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                return candidate;
            }
        }
        return -1;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 18 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED