LeetCode 268 · Bit Manipulation

Missing Number, explained with a picture

Roll call: who is missing?.

EasyBit Manipulation
▶ Watch it step by step

The problem

A list contains n different numbers taken from 0, 1, …, n, so exactly one is missing. Find the missing number.

Input:  [3, 0, 1]
Output: 2

Picture it

Picture a roll call: students numbered 0 to n should all be present but one is missing. Add up 0 + 1 + … + n (what the total should be) and subtract the numbers that actually answered. The difference is the missing student’s number.

How to recognise it

  • The values come from a known complete range (0 to n) with exactly one missing, and each value appears at most once.
  • If you know what the complete set adds up to, the missing value is the difference between that and what you have.
  • The same "cancel what is present" idea works with XOR (^), which is why it sits with bit manipulation.
  • n is up to 10^4, and the follow-up asks for O(n) time and O(1) extra space.

Start with brute force

Check each candidate 0, 1, ..., n and return the first one that is not in the list.

def missing_brute(nums):
    for i in range(len(nums) + 1):
        if i not in nums:
            return i

i not in nums scans the list, so this is O(n²) time: up to about 5 × 10^7 comparisons for n = 10^4, slow in Python. A set makes each lookup O(1) and the whole thing O(n), but it needs O(n) extra space.

From brute force to the idea

  1. Find the waste. We search for each candidate separately, but we only need one number: what is absent.
  2. Know the full total. The numbers 0 to n add up to n(n + 1)/2 (Gauss's formula). Here n is len(nums), because the list holds n of the n + 1 values.
  3. Subtract what is present. Every value in the list cancels its share of the total. What remains is the one value that never got subtracted.
  4. Use integer division. n * (n + 1) // 2 is exact, because one of n and n + 1 is even.

This is the key idea: expected sum minus actual sum is the missing number, in one pass and one variable.

Python integers never overflow, so the total is safe. In languages with 32-bit integers the XOR version below avoids any risk of overflow.

The key idea

n(n + 1)/2 − sum(nums) (or XOR indices and values). O(n), O(1).

Python solution

def missing_number(nums):
    n = len(nums)
    total = n * (n + 1) // 2      # roll call should add up to this
    for x in nums:
        total -= x
    return total

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (in on a list)O(n²): a scan for each candidateO(1)
Set of present valuesO(n)O(n): the set
Expected sum (shown code)O(n): one subtraction per numberO(1): one running total

Edge cases

  • The missing number is n ([0, 1]): the total 3 minus 0 and 1 leaves 2.
  • The missing number is 0 ([1]): the total 1 minus 1 leaves 0.
  • Single element [0]: returns 1.
  • Unsorted input ([9, 6, 4, 2, 3, 5, 7, 0, 1]): order does not matter; returns 8.
  • Broken promise (a duplicate, or a value above n): the result is meaningless, for example [5, 0] returns −2. The code does not check.

Common mistakes

  • Using n = the largest value in the list instead of len(nums): if n itself is missing, the largest value is n − 1 and the total is wrong.
  • Using the formula for 1 to n with the wrong n, such as n * (n - 1) // 2.
  • Sorting first and looking for a gap: correct, but O(n log n), and easy to miss the case where the gap is at the end.
  • Using / instead of //, which gives a float such as 2.0.
Your turn: the XOR version

Find the missing number again, but using XOR instead of a sum, so no total can grow large. Describe your approach, then write it if you like.

Compare with our answer

XOR every index 0 to n − 1, the value n, and every number in the list. Each present value appears twice (once as an index or as n, once in the list) and cancels; the missing one appears once and remains.

def missing_xor(nums):
    acc = len(nums)                 # n itself, the one index enumerate never gives
    for i, x in enumerate(nums):
        acc ^= i ^ x
    return acc

Time O(n), space O(1). missing_xor([3, 0, 1]) is 2.

A strong answer mentions: pairing each expected value with the list values so they cancel, including n (which enumerate does not produce), and that XOR never overflows.

Check what stuck

1. A ticket roll should hold numbers 1 to n with one ticket missing and no repeats. Which approach fits best?

2. Why must the shown code use n = len(nums) rather than max(nums)?

3. What does the shown code return for [0, 1]?

Score 60% or more and the lesson is marked complete.