Finding the Missing Number: A Coding Interview Guide

Algorithm Updated on April 20, 2025

Table of Contents

Problem Overview

The "Find the Missing Number" problem is a classic coding interview question that tests your problem-solving skills and ability to optimize for time and space. You're given an array of n-1 integers, representing numbers from 1 to n, with one number missing. Your task is to find the missing number efficiently.

Example:

  • Input: [3, 1, 4, 6, 2]
  • Output: 5
  • Explanation: The array contains numbers from 1 to 6, but 5 is missing.

Constraints:

  • Array length is n-1.
  • Numbers range from 1 to n, are unique, and the array is unsorted.
  • Ideal solution should have O(n) time and O(1) space complexity.

This post explores multiple solutions, provides Python implementations with tests, and shares tips for acing this question in interviews.

Approaches to Solve

Sum Formula Approach

Idea:
Use the arithmetic series sum formula, n * (n + 1) / 2, to calculate the expected sum of numbers from 1 to n. Subtract the actual sum of the array to find the missing number.

Steps:

  1. Compute n as array length + 1.
  2. Calculate expected sum: n * (n + 1) / 2.
  3. Compute actual sum of array elements.
  4. Return expected_sum - actual_sum.

Complexity:

  • Time: O(n) (single pass to sum array).
  • Space: O(1) (only a few variables).

Pros: Simple, intuitive.
Cons: Risk of integer overflow for large n.

XOR Approach

Idea:
XOR a number with itself yields 0, and XOR with 0 yields the number. XOR all numbers from 1 to n and all array elements; the result is the missing number, as paired numbers cancel out.

Steps:

  1. Initialize result as n (array length + 1).
  2. XOR result with numbers 1 to n and array elements.
  3. Return result.

Complexity:

  • Time: O(n) (single pass).
  • Space: O(1) (one variable).

Pros: Avoids overflow, elegant.
Cons: Less intuitive for beginners.

Sorting Approach

Idea:
Sort the array and check for the first index where nums[i] != i + 1. The missing number is i + 1.

Steps:

  1. Sort the array.
  2. Iterate and check if nums[i] == i + 1.
  3. Return i + 1 when mismatch found, or n if no mismatch.

Complexity:

  • Time: O(n log n) (sorting).
  • Space: O(1) or O(n) (depends on sorting algorithm).

Pros: Works well if array is sorted.
Cons: Suboptimal due to sorting overhead.

Python Implementation and Tests

Below are Python implementations for the sum and XOR approaches, as they’re the most efficient. The sorting approach is less common due to its time complexity but can be derived similarly.

Sum Formula Code

def findMissingNumberSum(nums):
    n = len(nums) + 1
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(nums)
    return expected_sum - actual_sum

XOR Code

def findMissingNumberXOR(nums):
    result = len(nums) + 1
    for i in range(len(nums)):
        result ^= (i + 1)
        result ^= nums[i]
    return result

Test Cases

def test_findMissingNumber():
    # Test case 1: Standard case
    assert findMissingNumberSum([3, 1, 4, 6, 2]) == 5
    assert findMissingNumberXOR([3, 1, 4, 6, 2]) == 5

    # Test case 2: Missing first number
    assert findMissingNumberSum([2, 3, 4, 5]) == 1
    assert findMissingNumberXOR([2, 3, 4, 5]) == 1

    # Test case 3: Missing last number
    assert findMissingNumberSum([1, 2, 3, 4]) == 5
    assert findMissingNumberXOR([1, 2, 3, 4]) == 5

    # Test case 4: Single element
    assert findMissingNumberSum([1]) == 2
    assert findMissingNumberXOR([1]) == 2

    # Test case 5: Empty array
    assert findMissingNumberSum([]) == 1
    assert findMissingNumberXOR([]) == 1

    print("All test cases passed!")

# Run tests
test_findMissingNumber()

Explanation of Tests:

  • Standard case: [3, 1, 4, 6, 2] (missing 5).
  • Missing first: [2, 3, 4, 5] (missing 1).
  • Missing last: [1, 2, 3, 4] (missing 5).
  • Single element: [1] (missing 2).
  • Empty array: [] (missing 1, assuming n=1).

Both implementations handle these cases correctly.

Choosing the Right Approach

  • Sum Formula: Use for simplicity and clarity. Ideal for most interviews unless overflow is a concern.
  • XOR: Choose if you want to avoid overflow or demonstrate bit manipulation skills. Slightly more complex but robust.
  • Sorting: Only use if the array is already sorted or the problem allows O(n log n) time, which is rare.

In interviews, the sum or XOR approach is typically expected due to their O(n) time and O(1) space complexity.

Edge Cases and Interview Tips

Edge Cases:

  • Empty array: Return 1 (if n=1).
  • Single element: Check if it’s 1 or 2.
  • Missing first (1) or last (n) number.
  • Large n: Watch for overflow in sum approach.

Tips:

  • Clarify: Ask if the array is sorted, has duplicates, or if space/time is prioritized.
  • Explain: Walk through your logic before coding (e.g., “I’ll use the sum formula because…”).
  • Test: Verify with examples like [3, 1, 4, 6, 2] (should return 5).
  • Optimize: Aim for O(n) time, O(1) space.
  • Handle Errors: Discuss edge cases like empty arrays or invalid inputs.

Conclusion

The "Find the Missing Number" problem is a great opportunity to showcase your problem-solving skills in coding interviews. By mastering the sum formula and XOR approaches, you can tackle this question efficiently with O(n) time and O(1) space. The provided Python code and test cases ensure your solution is robust, while the interview tips help you communicate your thought process effectively. Practice this problem, understand the trade-offs of each approach, and you’ll be well-prepared to impress your interviewer!