Introduction

This is a classic interview problem: you have an array with n - 1 numbers taken from the range 1 through n, and exactly one number is missing. The goal is to recover the missing value efficiently.

The simplest solutions use arithmetic or XOR. Both give linear time, and the best choice usually comes down to readability versus bit-manipulation comfort.

Sum Formula Method

The sum of numbers from 1 through n is:

n * (n + 1) / 2

If you subtract the actual array sum from the expected sum, the difference is the missing number.

Python example:

1def find_missing_sum(nums, n):
2    expected = n * (n + 1) // 2
3    actual = sum(nums)
4    return expected - actual
5
6
7arr = [3, 7, 1, 2, 8, 4, 5]
8print(find_missing_sum(arr, 8))

This prints 6.

This is easy to explain and usually the most readable solution.

XOR Method

The XOR approach is another O(n) time and O(1) extra-space solution.

The key identity is:

a ^ a = 0
0 ^ b = b

If you XOR all numbers in the array and all numbers from 1 through n, every number that appears in both places cancels out. The missing number is the only value left.

1def find_missing_xor(nums, n):
2    result = 0
3
4    for value in nums:
5        result ^= value
6
7    for value in range(1, n + 1):
8        result ^= value
9
10    return result
11
12
13arr = [3, 7, 1, 2, 8, 4, 5]
14print(find_missing_xor(arr, 8))

This also prints 6.

The XOR method is a strong interview answer because it avoids overflow concerns in languages where the sum formula could exceed integer limits.

Hash Set Method

If you want a direct correctness-first solution and extra space is acceptable, a set works too:

1def find_missing_set(nums, n):
2    values = set(nums)
3    for candidate in range(1, n + 1):
4        if candidate not in values:
5            return candidate
6
7
8arr = [3, 7, 1, 2, 8, 4, 5]
9print(find_missing_set(arr, 8))

This is also easy to understand, but it uses O(n) extra space instead of O(1).

Which Method Should You Prefer

Use the sum formula when:

• readability matters most
• integer overflow is not a concern
• and the input constraints are simple

Use XOR when:

• you want O(1) extra space
• you want to avoid overflow in fixed-width integer languages
• or the problem is explicitly interview-style

Use a set when:

• you want a very direct implementation
• the input rules may later become more flexible
• and extra memory is acceptable

What If the Range Starts at Zero

Some versions of the problem use numbers from 0 through n instead of 1 through n. The same strategies still work, but the expected range changes.

For example:

1def find_missing_zero_based(nums, n):
2    expected = n * (n + 1) // 2
3    return expected - sum(nums)
4
5
6arr = [0, 1, 2, 4]
7print(find_missing_zero_based(arr, 4))

This prints 3.

Always check the exact problem statement before applying the formula automatically.

Common Pitfalls

One common mistake is using the wrong range. A formula for 1 through n is not the same as a formula for 0 through n.

Another mistake is assuming the array always satisfies the problem contract. If the input can contain duplicates or out-of-range values, the classic missing-number tricks may produce misleading answers.

It is also easy to prefer a clever XOR solution when a straightforward sum solution would be clearer for the team maintaining the code.

Finally, in fixed-width integer languages, the sum formula can overflow for large n unless you choose a sufficiently large numeric type. Python avoids that issue because integers grow automatically.

Summary

• The missing number can be found in linear time with either arithmetic or XOR.
• The sum formula is often the clearest solution.
• XOR gives the same time complexity with constant extra space and avoids overflow concerns in some languages.
• A set-based solution is simple but uses more memory.
• Always confirm whether the range is 1 through n or 0 through n before implementing the formula.