Find Missing Number in Array using Sum Formula - Optimal Algorithm

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpaceDetailed Ex

Visualization Player

Problem Statement❯

You are given an array of N-1 distinct integers in the range 1 to N. The task is to find the one number that is missing from the array.

The array has no duplicates, and only one number is missing. The numbers can be in any order.

Your goal is to identify the missing number efficiently.

Examples❯

Input Array Expected N Missing Number Description
[1, 2, 4, 5] 5 3 All numbers from 1 to 5 are present except 3Visualization
[2, 3, 1, 5] 5 4 Missing number is in the middleVisualization
[1, 2, 3, 4] 5 5 Last number is missingVisualization
[2, 3, 4, 5] 5 1 First number is missingVisualization
[1] 2 2 Only one number present, second one is missingVisualization
[] 1 1 Empty array, so the only number 1 is missingVisualization
[2] 2 1 Only number 2 is present, so 1 is missingVisualization

Solution❯

Understanding the Problem

We are given an array of size N - 1 that contains distinct integers ranging from 1 to N. But one number is missing. Our task is to figure out which number is missing from the array.

Let’s understand this intuitively. If no number was missing, then the sum of all numbers from 1 to N would be:

Expected Sum = N * (N + 1) / 2

If we subtract the actual sum of the given array from this expected sum, the difference will be the missing number.

Step-by-Step Walkthrough

Example: Find the Missing Number from [1, 2, 4, 5], where N = 5

  • Step 1: Calculate expected sum = 5 × (5 + 1) / 2 = 15
  • Step 2: Calculate actual sum = 1 + 2 + 4 + 5 = 12
  • Step 3: Missing number = 15 - 12 = 3

So, 3 is the missing number.

Incorporating Edge Cases with Intuition

1. First Number Missing

Array = [2, 3, 4, 5], N = 5
Expected = 15, Actual = 14 ⇒ Missing = 1

This works because the formula always includes the first number. If it’s missing, the difference will reflect that.

2. Last Number Missing

Array = [1, 2, 3, 4], N = 5
Expected = 15, Actual = 10 ⇒ Missing = 5

The formula ensures we’re not depending on array order, so even the last number being missing is handled smoothly.

3. Only One Element in Array

Array = [1], N = 2
Expected = 3, Actual = 1 ⇒ Missing = 2

This proves our approach is valid even for the smallest possible size of input.

4. Empty Array

Array = [], N = 1
Expected = 1, Actual = 0 ⇒ Missing = 1

This is the edge case with the smallest possible value of N. Still, our formula gives the correct result.

5. Random Order

Array = [3, 1, 5, 2], N = 5
Expected = 15, Actual = 11 ⇒ Missing = 4

Since addition is commutative, the order of numbers doesn't matter. This makes our approach robust even when the array isn't sorted.

Why This Works

We are using math to solve the problem in a single pass over the array. This makes the solution:

  • Time Complexity: O(N) – because we sum the array once
  • Space Complexity: O(1) – no extra memory is needed

We don't need extra data structures like hash sets or frequency counters. The formula handles all cases efficiently, and it's especially useful for large datasets.

Algorithm Steps❯

  1. Given an array of size N-1, containing unique numbers between 1 to N.
  2. Calculate the sum of the first N natural numbers using the formula N*(N+1)/2.
  3. Calculate the sum of all elements in the given array.
  4. The missing number is the difference between the expected sum and the actual sum.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int findMissingNumber(int arr[], int N) {
    int total = N * (N + 1) / 2;
    int sum = 0;
    for (int i = 0; i < N - 1; i++) {
        sum += arr[i];
    }
    return total - sum;
}

int main() {
    int arr[] = {1, 2, 4, 5, 6};
    int N = 6;
    printf("Missing Number: %d\n", findMissingNumber(arr, N));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)We need to iterate through the array once to calculate the actual sum, which takes linear time.
Average CaseO(n)Regardless of the input distribution, we always sum all elements, resulting in linear time complexity.
Worst CaseO(n)In the worst case, the missing number is at the end, but we still iterate the full array, so the time remains linear.

Space Complexity❯

O(1)

Explanation: Only a constant number of variables are used to store sums and the final result. No extra space proportional to input size is required.

Detailed Step by Step Example❯

We are given an array of size 5 containing numbers from 1 to 6 with one number missing.

{ "array": [1,2,4,5,6], "showIndices": true }

Step 1: Calculate the expected sum from 1 to N = 6 * (6 + 1) / 2 = 21.

Step 2: Calculate the actual sum of the array = 18.

Step 3: The missing number is 21 - 18 = 3.

Final Result:

Missing Number = 3


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...