Missing Number in Array

Difficulty: Easy

Problem

You are given an array `arr` containing `n-1` distinct positive integers. These numbers are from the range `1` to `n`, but exactly **one number is missing**. Your task is to find and return that missing number.

For example, if the array has 4 elements, then n = 5 (since array size = n - 1), and the numbers should be 1, 2, 3, 4, 5 — but one of them is not 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)