Find the Missing Number

DevSniper

Published : 15 February 2024
Updated : 30 May 2025

197 Views

Array Searching Data Structures Coding Problems Low

Given a size N-1 array arr[] with an integer range of 1 to N. Write a code to find missing number from that array.

Note :-There are no duplicate entries in the array.

Example

Input :- arr = [1,2,6,7,9,8,3,5]

Output :- 4

Constraints : -

=> 1 ≤ N ≤ 106
=> 1 ≤ A[i] ≤ 106

Approach 1 : Using an other array of size N

Since all numbers lie between 1 and N, we can create a temporary array of size N to track which numbers are present.

Each time we encounter a number in arr[], we mark its position as true. The index that remains false indicates the missing number.

Java

C++

import java.io.*;
import java.util.*;

public class MissingNumberProblem {
    public static void findMissing(int arr[]) {
        boolean temp[] = new boolean[arr.length + 1];
        Arrays.fill(temp,false);
        for (int i = 0; i < arr.length; i++) {
            temp[arr[i] - 1] = true;
        }
        int ans = 0;
        for (int i = 0; i <= arr.length; i++) {
            if (!temp[i]) {
                ans = i + 1;
                break;
            }
        }
        System.out.println(ans);
    }
    public static void main(String[] args) {
        int arr[] = { 1,7,2,5,6,8,4 };
        findMissing(arr);
    }
}

Time Complexity: O(N)
Auxiliary Space: O(N)

Approach 2 : First n natural number's summation

Idea behind this approach is to find out sum of first N natural numbers with formula N*(N+1)/2 after that find the sum of all elements of the array and subtract it from the sum of first N natural numbers. this will be our missing number.

C++

Java

#include <bits/stdc++.h>

using namespace std;

int findMissing(int arr[], int n)
{
    int N = n+1;
    int nNumberSum = (N*(N+1))/2;
    int arrSum = 0;
    for(int i=0; i<n; i++) {
        arrSum+=arr[i];
    }
    return nNumberSum-arrSum;
}
int main()
{
    int arr[] = { 1,7,2,5,6,8,4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<findMissing(arr,n);
    return 0;
}

Time Complexity: O(N)
Auxiliary Space: O(1)

There will be integer overflow if N is large.

Avoiding Integer Overflow

To avoid integer overflow, use a running difference

pick one number from the range of 1 to N and subtract one number from the array arr ( every number should be subtracted only once)

C++

Java

#include <bits/stdc++.h>

using namespace std;

int findMissing(int arr[], int n)
{
    int N = n+1;
    int missingNumber = 1;
    for(int i=2; i<=n+1; i++) {
        missingNumber+=i;
        missingNumber-=arr[i-2];
    }
    return missingNumber;
}
int main()
{
    int arr[] = { 1,7,2,5,6,8,4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<findMissing(arr,n);
    return 0;
}

Time Complexity: O(N)
Auxiliary Space: O(1)

Approach 3 : XOR Method (Bitwise Magic)

Important Properties of XOR that we can use here

XOR of same numbers is 0
XOR of a number with 0 will be that number
XOR is commutative and associative (This means the order doesn’t matter)

a ^ a = 0
a ^ 0 = a
a ^ b ^ c = c ^ a ^ b = b ^ c ^ a

So if we take XOR of all numbers from 1 to N and XOR of all numbers in the array. The remaining number is the missing one.

Explanation

Input : arr = [1, 2, 4, 5, 6]
Here, N = 6 -> Missing number = 3

XOR all numbers from 1 to N and Let’s call this xor1
```
1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6
```
XOR all elements of the array and Let’s call this xor2
```
1 ^ 2 ^ 4 ^ 5 ^ 6
```

XOR both results

xor1 ^ xor2 = (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6) ^ (1 ^ 2 ^ 4 ^ 5 ^ 6)

Now cancel common numbers (because a ^ a = 0):

(1 ^ 1) ^ (2 ^ 2) ^ (4 ^ 4) ^ (5 ^ 5) ^ (6 ^ 6) ^ 3

All pairs become 0, leaving only:
```
0 ^ 0 ^ 0 ^ 0 ^ 0 ^ 3 = 3
```
Missing Number = 3

C++

Java

Python

#include <bits/stdc++.h>
using namespace std;

int findMissing(int arr[], int n) {
    int xor1 = 0, xor2 = 0;
    for (int i = 1; i <= n + 1; i++)
        xor1 ^= i;
    for (int i = 0; i < n; i++)
        xor2 ^= arr[i];
    return xor1 ^ xor2;
}
int main() {
    int arr[] = {1, 2, 4, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Missing Number: " << findMissing(arr, n);
}

Missing Number: 3

Time Complexity : O(N)
Space Complexity : O(1)

Comparison of Approaches

Approach	Time	Space	Handles Overflow	Difficulty	Notes
Boolean Array	O(N)	O(N)	Yes	Easy	Good for beginners
Sum Formula	O(N)	O(1)	No	Medium	Simple but overflow risk
Avoiding Integer Overflow	O(N)	O(1)	Yes	Medium	Practical for large N
XOR Method	O(N)	O(1)	Yes	Advanced	Clean, efficient, elegant