Find the Missing Number

DevSniper
Published : 15 February 2024

187 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

Number will be in the range of 1 to N. we can maintaine a array of size N to keep track of elemants present in array arr[]

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 , 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)