Missing Number in Array

Difficulty: Easy

Problem

You receive an array `arr` of `n-1` distinct positive integers, each taken from `1` through `n`, so exactly **one value in that range is absent**. Find the absent value and return it.

For example, if the array holds 4 elements, then n = 5 (since array size = n - 1), and the full set would be 1, 2, 3, 4, 5, with one of them not present in the array.

Example

Input: arr = [5, 2, 1, 3]
Output: 4
Explanation: The array has 4 elements, so n = 5. The numbers should be 1, 2, 3, 4, 5. Looking at the array: we have 1 ✓, 2 ✓, 3 ✓, 5 ✓... but 4 is nowhere to be found! So the missing number is 4.

Brute-force approach

For each number from 1 to n, scan the entire array to check if it exists. The first number not found is our answer.

Steps

  1. Calculate n = arr.length + 1
  2. For each candidate c from 1 to n:
  3. - Scan the entire array looking for c
  4. - If c is not found, return c as the missing number
  5. Return -1 if all found (shouldn't happen with valid input)

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Nested loops: for each of n candidates, we scan n elements
  • Very slow for large arrays (1 million elements = 1 trillion operations)
  • Doesn't leverage any mathematical properties of the problem

Optimal approach

Key insight: The sum of numbers 1 to n has a mathematical formula: n×(n+1)/2. If we calculate the expected sum and subtract the actual sum of the array, the difference is exactly the missing number!

Use the sum formula for 1..n. Subtract the actual sum of the array to get the missing number.

Steps

  1. Calculate n = arr.length + 1
  2. Calculate expectedSum = n × (n + 1) / 2
  3. Calculate actualSum by adding all elements in arr
  4. Return expectedSum - actualSum

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function solution(arr):
    n = length(arr) + 1
    
    # Calculate expected sum of 1 to n
    expectedSum = n * (n + 1) / 2
    
    # Calculate actual sum of array elements
    actualSum = 0
    for num in arr:
        actualSum = actualSum + num
    
    # The difference is the missing number
    return expectedSum - actualSum

Hints

  • Array has n-1 elements, so n = arr.length + 1
  • Sum of 1 to n = n × (n+1) / 2
  • missing = expectedSum - actualSum
  • Single pass through array: O(n) time, O(1) space

Complexity questions

What is the time complexity of the brute force approach?

O(n²). For each of n candidates, we scan up to n elements. That's n × n = O(n²).

What is the time complexity of the optimal (sum formula) approach?

O(n). We traverse the array once to calculate the sum. O(n).

What is the space complexity of the optimal approach?

O(1). We only use a few variables (n, expectedSum, actualSum). Constant space!

How much faster is the optimal approach for an array of 1 million elements?

About 1,000,000 times faster. Brute force: 10¹² operations. Optimal: 10⁶ operations. That's 1 million times faster!

Check your understanding of Missing Number in Array

If the array has 4 elements, what is n (the upper bound of the range)?

5. Array size = n - 1, so n = 4 + 1 = 5. The range is 1 to 5.

For arr = [5, 2, 1, 3], which number is missing?

4. n=5, so we expect 1,2,3,4,5. The array has 1,2,3,5 but NOT 4.

For arr = [3, 1, 2, 5, 4, 7, 6], what number is missing?

8. The array has 7 elements, so n = 8. The range is 1 to 8. All numbers 1-7 are present, so 8 is missing.

Related problems

Keep practising