Find Missing Number in Array

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.

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.

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.

Worked example

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

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

#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;
}

#include <iostream>
#include <vector>
using namespace std;

int findMissingNumber(const vector<int>& arr, int N) {
    int total = N * (N + 1) / 2;
    int sum = 0;
    for (int num : arr) {
        sum += num;
    }
    return total - sum;
}

int main() {
    vector<int> arr = {1, 2, 4, 5, 6};
    int N = 6;
    cout << "Missing Number: " << findMissingNumber(arr, N) << endl;
    return 0;
}

def find_missing_number(arr, N):
    total = N * (N + 1) // 2
    actual_sum = sum(arr)
    return total - actual_sum

# Sample Input
arr = [1, 2, 4, 5, 6]
N = 6
print("Missing Number:", find_missing_number(arr, N))

public class MissingNumber {
    public static int findMissingNumber(int[] arr, int N) {
        int total = N * (N + 1) / 2;
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        return total - sum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 6};
        int N = 6;
        System.out.println("Missing Number: " + findMissingNumber(arr, N));
    }
}

function findMissingNumber(arr, N) {
    const expectedSum = (N * (N + 1)) / 2;
    const actualSum = arr.reduce((a, b) => a + b, 0);
    return expectedSum - actualSum;
}

// Sample Input
const arr = [1, 2, 4, 5, 6];
const N = 6;
console.log('Missing Number:', findMissingNumber(arr, N));

package main

import (
    "fmt"
)

func findMissingNumber(arr []int, N int) int {
    total := N * (N + 1) / 2
    sum := 0
    for _, num := range arr {
        sum += num
    }
    return total - sum
}

func main() {
    arr := []int{1, 2, 4, 5, 6}
    N := 6
    fmt.Println("Missing Number:", findMissingNumber(arr, N))
}

fn find_missing_number(arr: &[i32], n: i32) -> i32 {
    let total = n * (n + 1) / 2;
    let sum: i32 = arr.iter().sum();
    total - sum
}

fn main() {
    let arr = [1, 2, 4, 5, 6];
    let n = 6;
    println!("Missing Number: {}", find_missing_number(&arr, n));
}

fun findMissingNumber(arr: IntArray, N: Int): Int {
    val total = N * (N + 1) / 2
    val sum = arr.sum()
    return total - sum
}

fun main() {
    val arr = intArrayOf(1, 2, 4, 5, 6)
    val N = 6
    println("Missing Number: ${findMissingNumber(arr, N)}")
}

func findMissingNumber(arr: [Int], N: Int) -> Int {
    let total = N * (N + 1) / 2
    let sum = arr.reduce(0, +)
    return total - sum
}

let arr = [1, 2, 4, 5, 6]
let N = 6
print("Missing Number: \(findMissingNumber(arr: arr, N: N))")

function findMissingNumber(arr: number[], N: number): number {
    const expectedSum = (N * (N + 1)) / 2;
    const actualSum = arr.reduce((a, b) => a + b, 0);
    return expectedSum - actualSum;
}

const arr: number[] = [1, 2, 4, 5, 6];
const N: number = 6;
console.log('Missing Number:', findMissingNumber(arr, N));

Time complexity

Space complexity

O(1)

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