LeetCode 268: Missing Number

Problem Restatement

We are given an array nums containing n distinct numbers from the range:

0, 1, 2, ..., n

Exactly one number from this range is missing.

Return the missing number.

For example, if:

nums = [3, 0, 1]

then n = 3, so the full range should be:

[0, 1, 2, 3]

The missing number is:

2

The problem asks for an algorithm with linear runtime. The common follow-up is to use only constant extra space.

Input and Output

Example function shape:

def missingNumber(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [3, 0, 1]

The complete range is:

[0, 1, 2, 3]

The missing number is:

2

Answer:

2

Example 2:

nums = [0, 1]

The complete range is:

[0, 1, 2]

The missing number is:

2

Answer:

2

Example 3:

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

The complete range is:

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

The missing number is:

8

Answer:

8

First Thought: Use a Set

A simple solution stores all numbers in a set.

Then check each value from 0 to n.

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        seen = set(nums)

        for x in range(len(nums) + 1):
            if x not in seen:
                return x

        return -1

This is easy and correct, but it uses extra space.

Problem With the Set Solution

The set stores up to n numbers.

So the space complexity is:

O(n)

We can solve the problem using only arithmetic.

Key Insight

The numbers should contain every value from 0 to n, except one.

The sum of the complete range is:

0 + 1 + 2 + ... + n

This sum has a direct formula:

n * (n + 1) // 2

If we subtract the actual sum of nums, the remaining value is the missing number.

Algorithm

1. Let n = len(nums).
2. Compute the expected sum:

   expected = n * (n + 1) // 2
3. Compute the actual sum:

   actual = sum(nums)
4. Return:

   expected - actual

Walkthrough

Use:

nums = [3, 0, 1]

The array length is:

n = 3

Expected sum:

3 * (3 + 1) // 2 = 6

Actual sum:

3 + 0 + 1 = 4

Difference:

6 - 4 = 2

Return:

2

Correctness

The complete range 0 through n contains every valid number exactly once.

The input array contains the same range except for one missing value.

So:

expected_sum = actual_sum + missing

Rearranging gives:

missing = expected_sum - actual_sum

The algorithm computes exactly this difference.

Therefore it returns the missing number.

Complexity

Implementation

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        n = len(nums)
        expected = n * (n + 1) // 2
        actual = sum(nums)

        return expected - actual

Code Explanation

The value n is the array length:

n = len(nums)

Since the numbers come from 0 to n, the complete range contains n + 1 numbers.

The expected sum is:

expected = n * (n + 1) // 2

The actual sum is:

actual = sum(nums)

The missing number is the difference:

return expected - actual

Alternative: XOR Solution

We can also solve this with XOR.

XOR has these useful properties:

x ^ x = 0
x ^ 0 = x

If we XOR all numbers from 0 to n, and also XOR all numbers in nums, every present number cancels out.

Only the missing number remains.

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        missing = len(nums)

        for i, x in enumerate(nums):
            missing ^= i
            missing ^= x

        return missing

For example:

nums = [3, 0, 1]

Start with:

missing = 3

Then XOR indices and values:

3 ^ 0 ^ 3 ^ 1 ^ 0 ^ 2 ^ 1

All matching values cancel.

The result is:

2

Testing

def run_tests():
    s = Solution()

    assert s.missingNumber([3, 0, 1]) == 2
    assert s.missingNumber([0, 1]) == 2
    assert s.missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]) == 8
    assert s.missingNumber([0]) == 1
    assert s.missingNumber([1]) == 0
    assert s.missingNumber([1, 2, 3]) == 0
    assert s.missingNumber([0, 1, 2]) == 3

    print("all tests passed")

run_tests()

Test meaning: