Find the Missing Number in 1 to N: The Math Trick That Makes It O(n)

You are given an array containing n-1 distinct integers taken from the range 1 to n. Exactly one number is missing. Find it.

This is one of those problems where the clever solution is genuinely elegant — not just marginally faster, but based on a mathematical insight that makes sorting unnecessary.

The Gaussian Sum Approach

The sum of integers from 1 to n is n * (n + 1) / 2. That is the expected total. Subtract the actual sum of the array and the difference is the missing number.

def find_missing_number(arr, n):
    """
    Find the single missing number in an array of 1..n with one element absent.
    arr: list of integers
    n:   the upper bound of the expected range
    """
    expected_sum = n * (n + 1) // 2   # Gauss formula
    actual_sum = sum(arr)
    return expected_sum - actual_sum

# Example
arr = [1, 2, 4, 5, 6]   # 3 is missing
n = 6
print(find_missing_number(arr, n))
# Output: 3

One pass through the array to compute sum(arr), one subtraction, done. Time: O(n). Space: O(1).

Walking Through the Logic

For [1, 2, 4, 5, 6] with n = 6:

• Expected sum: 6 × 7 / 2 = 21
• Actual sum: 1 + 2 + 4 + 5 + 6 = 18
• Missing number: 21 − 18 = 3

No sorting. No extra data structures. No nested loops.

Alternative: XOR Approach

XOR has a useful property: x ^ x = 0 and x ^ 0 = x. XOR all numbers from 1 to n, then XOR the result with every element in the array. The matching numbers cancel out, leaving only the missing one.

def find_missing_xor(arr, n):
    """XOR-based solution — also O(n) time, O(1) space, no overflow risk."""
    xor_total = 0
    for i in range(1, n + 1):
        xor_total ^= i         # XOR all expected numbers

    for num in arr:
        xor_total ^= num       # XOR with actual numbers; pairs cancel

    return xor_total

arr = [3, 7, 1, 2, 8, 4, 5]   # 6 is missing from 1..8
n = 8
print(find_missing_xor(arr, n))
# Output: 6

The XOR version avoids any risk of integer overflow (not a Python concern, but important in C/Java interviews). Both approaches are equally valid here.

Finding Multiple Missing Numbers

If the problem allows more than one missing value, the sum trick only tells you their combined total — not each individual value. Use a presence array or a set instead:

def find_multiple_missing(arr, n):
    """Return all missing numbers in 1..n."""
    present = set(arr)
    return [i for i in range(1, n + 1) if i not in present]

arr = [1, 2, 4, 6, 7, 8, 10]
n = 10
print(find_multiple_missing(arr, n))
# Output: [3, 5, 9]

Time: O(n). Space: O(n) for the set. The set lookup inside the comprehension is O(1) on average.

Common Interview Pitfalls

Off-by-one: make sure your expected range is 1..n inclusive. The formula is n * (n + 1) // 2, not n * (n - 1) // 2.

Assuming exactly one missing: always clarify with the interviewer whether there is guaranteed to be exactly one missing number. If not, the sum trick gives incorrect results for multiple gaps.

Using integer division: in Python 3, / returns a float. Use // to keep the result an integer and avoid floating-point comparison issues.