Missing Number

The problem

You are given a list nums of whole numbers in which no number appears twice. Call its length n. Every number in the list is one of the n + 1 numbers 0, 1, 2 and so on up to n, so exactly one number of that range is not in the list. Return that missing number. The numbers can come in any order. The list can be empty: then the range is the single number 0, and 0 is the missing number.

What to write

function solve(nums: number[]): number

Input
nums = [3,0,1]

Output
2

Input
nums = [0,1]

Output
2

Constraints

0–10,000 distinct integers drawn from 0 through n.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The list has n numbers, no two the same, and each is one of the n + 1 numbers from 0 through n. So exactly one number of that range is absent, and it can be 0 or n itself. With 10,000 numbers, searching the list for each candidate can add up to about 50 million comparisons.

2. Hint 2: Ask a smaller question

   Take the list [3, 0, 1] and write the full range 0, 1, 2, 3 next to it. Put all seven numbers in one pile. How many times is each number in the pile? Which number has a different count from all the others?

3. Hint 3: Name the pattern

   Put the list and the range 0 through n in one pile: every number is there twice except the missing one. XOR works on binary digits (bits) and keeps a 1 where two bits differ, so equal numbers XOR to 0 and pairs cancel. This is bit manipulation. The signal: everything is paired except one thing. Read the lesson on bit manipulation.

4. Hint 4: State the invariant

   XOR gives the same result in any order. So at every moment the value you keep is the XOR of the numbers put in once so far. A number put in twice has canceled and no longer counts.

5. Hint 5: Sketch the pseudocode

   Set kept to n, the length of nums. For each position i from 0 to n - 1: kept = kept XOR i XOR the number at position i. Return kept.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

XOR n, all indices, and all input values. Every present value cancels with the index equal to it, or with n itself, leaving only the missing number.

The slow way

For each number from 0 through n, search the list for it, and return the one you cannot find. It is correct, but the searches add up: with 10,000 numbers they can take about 50 million comparisons. A hash set of the numbers makes each check about one step, but it stores a copy of every number.

The insight

Put the list and the range 0 through n in one pile. Every number of the list is in the pile twice, and the missing number once. XOR compares two numbers one binary digit, or bit, at a time and keeps a 1 where the bits differ, so two equal numbers XOR to 0. XOR the whole pile, in any order, and only the missing number is left.

Step by step

1. Start with the length of the list, the last number of the range. The range is 0 through n, and n is the length. The loop supplies 0 through n - 1 as its positions, so n is the one number of the range that would be left out.
2. XOR in every position and the number stored at that position. XOR is written ^ in code. Together with the start value, the positions supply the whole range. The stored numbers supply the list. A number that is in both goes in twice, and two equal numbers XOR to 0.
3. The numbers that are present have canceled: return what is left. Only the missing number went in once, from the range and not from the list. Everything else has become 0, and 0 XOR a number is that number.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Start with the length of the list, the last number of the range
  let missing = nums.length;
  // 2. XOR in every position and the number stored at that position
  for (let i = 0; i < nums.length; i++) missing ^= i ^ nums[i];
  // 3. The numbers that are present have canceled: return what is left
  return missing;
}

function solve(nums: number[]): number {
  // 1. Start with the length of the list, the last number of the range
  let missing = nums.length;
  // 2. XOR in every position and the number stored at that position
  for (let i = 0; i < nums.length; i++) missing ^= i ^ nums[i];
  // 3. The numbers that are present have canceled: return what is left
  return missing;
}

def solve(nums):
    # 1. Start with the length of the list, the last number of the range
    missing = len(nums)
    # 2. XOR in every position and the number stored at that position
    for i, num in enumerate(nums):
        missing ^= i ^ num
    # 3. The numbers that are present have canceled: return what is left
    return missing

Example 1, traced

Input
nums = [3,0,1]

Output
2

Why it works

XOR gives the same result in any order, a number XOR itself is 0, and 0 XOR a number is that number. The value kept takes in every number from 0 through n once, as a position or as the start value, and every number of the list once. A present number goes in twice and cancels. The missing number goes in once and remains.

Time and space

Time O(n), extra space O(1). The loop visits each of the n numbers once and does two XORs for it, so the time is O(n). Only one running value and one position are kept, however long the list is. That is O(1), also called constant space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Start from n, not from 0. Started from 0, n is never put in, and the result is the right answer XOR n: [3, 0, 1] gives 1 instead of 2. Only the empty list comes out right.
• Take n from the length of the list, not from its largest number. When the missing number is n, as in [0, 1], the largest number is n - 1, and the XOR then leaves 1 instead of 2.

Pattern

Bit manipulation. Builds on Single Number.

Keep going