Missing Number

The problem

You are given an array nums of n different numbers. Each one is between 0 and n. There are n + 1 numbers in that range, so exactly one of them is not in nums. Return that number.

Example 1

Input: nums = [4, 0, 6, 1, 3, 2]

Output: 5

n = 6, so the range is 0 to 6. Every number in it shows up except 5.

0 to n

0123456

nums

400162133425

Example 2

Input: nums = [1, 0]

Output: 2

n = 2, so the range is 0 to 2. The missing number can be n itself.

Example 3

Input: nums = [1]

Output: 0

n = 1, so the range is 0 to 1. The missing number can be 0.

Constraints

• 1 ≤ n ≤ 10,000, where n is the length of nums
• 0 ≤ nums[i] ≤ n, and all numbers in nums are different

Clarifying questions

Is nums sorted?

No. The numbers come in any order.

Can a number appear twice?

No. All n numbers are different, so exactly one number in the range is missing.

Can we change nums, or use extra memory?

The follow-up asks for O(1) extra memory and O(n) time, without changing nums.

Spot the pattern

The answer is the one number that appears once in “0 to n” but not in nums. Every other number appears in both. XOR cancels a number that appears twice (a ^ a = 0), so XOR-ing everything together leaves only the number that appears once. That is bit manipulation.

Solutions

Scan for each numberO(n²)Hash setO(n), O(n) spaceXORO(n), O(1) space

Show all

Scan for each number O(n²)

The idea

Try each candidate from 0 to n. Scan nums from the start to see if candidate is there. The first candidate that the scan does not find is the answer.

It is correct, but every candidate scans the list again.

Walkthrough

0 to n

0123456

nums

400162133425

comparisons

0

1. for candidate in range(len(nums) + 1):
2. found = False
3. for value in nums:
4. if value == candidate:
5. found = True
6. break
7. if not found:
8. return candidate

nums has 6 numbers, so the numbers should be 0 to 6. For each one, scan nums to see if it is there.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Scan for each number: try 0 to n, and scan nums for each one.
    // Up to n + 1 scans of n values: O(n^2) time, O(1) memory.
    public int missingNumber(int[] nums) {
        int numsLength = nums.length;
        for (int candidate = 0; candidate <= numsLength; candidate++) {
            boolean found = false;
            for (int value : nums) {
                if (value == candidate) {
                    found = true;
                    break;
                }
            }
            if (!found) return candidate;
        }
        // Never reached: exactly one number in 0..n is missing.
        return -1;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line compares one value with candidate. That is 1 step. It sits inside two loops: one picks candidate, the other scans nums.

   1. for candidate in range(len(nums) + 1):
   2. found = False
   3. for value in nums:
   4. if value == candidate:
   5. found = True
   6. break
   7. if not found:
   8. return candidate

2. 2 Count the runs on Example 1

   Example 1 has n = 6. The table shows how many comparisons each candidate made. A found number stops early; the missing 5 scans all 6 values.

   2 + 4 + 6 + 5 + 1 + 6 = 24 comparisons.

   candidate	0	1	2	3	4	5
   comparisons	2	4	6	5	1	6

   total

   2 + 4 + 6 + 5 + 1 + 6 = 24

3. 3 Write the count for any n

   There are at most n + 1 candidates, and each scan makes at most n comparisons:

   at most (n + 1) × n = n² + n comparisons

   The worst case comes close to that: when n itself is missing, as in Example 2, every candidate before it is found somewhere in the list, and n scans all of it. Check it with Example 1: at most 7 × 6 = 42. The real 24 is lower because found numbers stop early.

4. 4 Keep only the part that grows fastest

   • Drop the +n. It is small next to n².

   What is left is n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code keeps candidate, value and found. The space is O(1).

   candidatevaluefound

Hash set O(n), O(n) space

The idea

Put all the values into a hash set first. Then try each candidate from 0 to n, and ask the set if candidate is there. A set answers in one step, so no scan is needed.

Walkthrough

nums

400162133425

seen

empty

1. seen = set(nums)
2. for candidate in range(len(nums) + 1):
3. if candidate not in seen:
4. return candidate

Put every value into a set first. Then each "is candidate there?" check is one lookup, not a scan.

← BackStep →Play1 / 13

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Hash set: one pass to fill the set, then one lookup per candidate.
    // Two loops one after the other: O(n) time, O(n) memory.
    public int missingNumber(int[] nums) {
        int numsLength = nums.length;
        java.util.Set<Integer> seen = new java.util.HashSet<>();
        for (int value : nums) seen.add(value);
        for (int candidate = 0; candidate <= numsLength; candidate++) {
            if (!seen.contains(candidate)) return candidate;
        }
        // Never reached: exactly one number in 0..n is missing.
        return -1;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two kinds of work repeat: adding a value to the set, and looking up candidate in the set. Both take 1 step on average. The two loops are one after the other, not nested.

   1. seen = set(nums)
   2. for candidate in range(len(nums) + 1):
   3. if candidate not in seen:
   4. return candidate

2. 2 Count the runs on Example 1

   Example 1 has n = 6. Building the set adds 6 values. The lookups run for 0 to 5 and stop at 5.

   6 + 6 = 12 runs.

   part	build the set	lookups
   runs	6	6

   total

   6 + 6 = 12

3. 3 Write the count for any n

   Building the set takes n runs. The lookups take at most n + 1 runs:

   n + (n + 1) = 2n + 1

   Check it with Example 1: at most 13 runs. The real 12 is one less because 5 is found before 6.

4. 4 Keep only the part that grows fastest

   Drop the 2 and the +1. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The set holds all n values. The space is O(n).

   seen (n values)candidate

XOR O(n), O(1) space

The idea

XOR has two rules: a ^ a = 0 and a ^ 0 = a. The order does not matter.

Start with xor_total = nums_length. Then XOR in every index i from 0 to n − 1, and every value nums[i]. Together, nums_length and the indexes are every number from 0 to n, once each. The values are the same numbers with one missing. So every number except the missing one goes in twice and cancels. What is left in xor_total is the missing number.

The sum works the same way: 0 + 1 + … + n minus the sum of nums. XOR has the advantage that it can never overflow.

Walkthrough

nums

400162133425

xor_total = 6

110

1. xor_total = len(nums)
2. for i in range(len(nums)):
3. xor_total ^= i ^ nums[i]
4. return xor_total

XOR has two rules: a ^ a = 0 and a ^ 0 = a. Start xor_total at len(nums) = 6, then XOR in every index and every value. Each number that is present shows up twice and cancels out.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // XOR: every number in 0..n except the missing one goes in twice and cancels.
    // One pass: O(n) time, O(1) memory.
    public int missingNumber(int[] nums) {
        int numsLength = nums.length;
        // Start at numsLength, because the indexes only cover 0 to numsLength - 1.
        int xorTotal = numsLength;
        for (int i = 0; i < numsLength; i++) xorTotal ^= i ^ nums[i];
        return xorTotal;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line does two XORs. That is 1 step. It sits inside one loop.

   1. xor_total = len(nums)
   2. for i in range(len(nums)):
   3. xor_total ^= i ^ nums[i]
   4. return xor_total

2. 2 Count the runs on Example 1

   Example 1 has n = 6. The table shows xor_total after each run.

   6 runs.

   i	0	1	2	3	4	5
   xor_total after	2	3	7	5	2	5

   total

   6 runs

3. 3 Write the count for any n

   The loop runs once per index:

   n runs

   Check it with Example 1: 6 runs, against 12 for the hash set and 24 for scanning.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is already n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The code keeps xor_total and i. The space is O(1).

   xor_totali

Common mistake

Forgetting to XOR in n

The loop only covers indexes 0 to n − 1, but the range goes up to n. If xor_total starts at 0 instead of n, then n never goes in as an index. For Example 2, [1, 0], that gives 0 ^ 1 ^ 1 ^ 0 = 0 instead of 2.

Tested at the limits

2,000 random arrays of 1 to 9 numbers, shuffled, with 0 or n missing about a third of the time. Scan for each number, hash set and XOR gave the same answer every time.

Largest inputs	Result
10,000 numbers (the most allowed), shuffled, with 10,000 itself missing. XOR.	Under 0.001 s, and under 0.001 MB of extra memory: just two numbers.
The same 10,000 numbers. Hash set.	Under 0.001 s too, but about 0.6 MB for the set of all n values.
2,000 numbers. Scan for each number.	0.04 s. At 10,000 numbers it would make up to 100 million checks.