Find the Missing Number

Given an array arr[] of size N-1 with integers in the range of [1, N], the task is to find the missing number from the first N integers.

Note: There are no duplicates in the list.

Examples: 

Input: arr[] = {1, 2, 4, 6, 3, 7, 8} , N = 8
Output: 5
Explanation: Here the size of the array is 8, so the range will be [1, 8]. The missing number between 1 to 8 is 5

Input: arr[] = {1, 2, 3, 5}, N = 5
Output: 4
Explanation: Here the size of the array is 4, so the range will be [1, 5]. The missing number between 1 to 5 is 4

Approach 1 – Using Hashing: O(n) time and O(n) space

The numbers will be in the range (1, N), an array of size N can be maintained to keep record of the elements present in the given array

Steps:

• Create a temp array temp[] of size n + 1 with all initial values as 0.
• Traverse the input array arr[], and do following for each arr[i] 
  • if(temp[arr[i]] == 0) temp[arr[i]] = 1 
• Traverse temp[] and output the array element having value as 0 (This is the missing element).

Implementation:

// C++ program to Find the missing element

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

void findMissing(int arr[], int N)
{
    int i;
    int temp[N + 1];
    for(int i = 0; i <= N; i++){
      temp[i] = 0;
    }
  
    for(i = 0; i < N; i++){
      temp[arr[i] - 1] = 1;
    }


    int ans;
    for (i = 0; i <= N ; i++) {
        if (temp[i] == 0)
            ans = i  + 1;
    }
    cout << ans;
}

/* Driver code */
int main()
{
    int arr[] = { 1, 3, 7, 5, 6, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findMissing(arr, n);
}

#include <stdio.h>

void findMissing(int arr[], int N)
{
    int temp[N + 1];
    for (int i = 0; i <= N; i++) {
        temp[i] = 0;
    }

    for (int i = 0; i < N; i++) {
        temp[arr[i] - 1] = 1;
    }

    int ans;
    for (int i = 0; i <= N; i++) {
        if (temp[i] == 0)
            ans = i + 1;
    }
    printf("%d", ans);
}

/* Driver code */
int main()
{
    int arr[] = { 1, 3, 7, 5, 6, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    findMissing(arr, n);
}

// This code is contributed by nikhilm2302

// Java code to implement the approach
import java.io.*;
import java.util.*;

class GFG {

    // Function to find the missing number
    public static void findMissing(int arr[], int N)
    {
        int i;
        int temp[] = new int[N + 1];
        for (i = 0; i <= N; i++) {
            temp[i] = 0;
        }

        for (i = 0; i < N; i++) {
            temp[arr[i] - 1] = 1;
        }

        int ans = 0;
        for (i = 0; i <= N; i++) {
            if (temp[i] == 0)
                ans = i + 1;
        }
        System.out.println(ans);
    }
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 1, 3, 7, 5, 6, 2 };
        int n = arr.length;

        // Function call
        findMissing(arr, n);
    }
}

# Find Missing Element
def findMissing(arr, N):

    # create a list of zeroes
    temp = [0] * (N+1)

    for i in range(0, N):
        temp[arr[i] - 1] = 1

    for i in range(0, N+1):
        if(temp[i] == 0):
            ans = i + 1

    print(ans)


# Driver code
if __name__ == '__main__':
    arr = [1, 2, 3, 5]
    N = len(arr)

    # Function call
    findMissing(arr, N)

    # This code is contributed by nikhilm2302

using System;
public class GFG {

    public static void findMissing(int[] arr, int N)
    {

        // this will create a new array containing 0
        int[] temp = new int[N + 1];

        for (int i = 0; i < N - 1; i++) {
            temp[arr[i] - 1] = 1;
        }

        int ans = 0;
        for (int i = 0; i <= N; i++) {
            if (temp[i] == 0)
                ans = i + 1;
        }
        Console.WriteLine(ans);
    }
    static public void Main()
    {
        int[] arr = { 1, 3, 7, 5, 6, 2 };
        int n = arr.Length;

        findMissing(arr, n);
    }
}

// This code is contributed by nikhilm2302.

// Javascript code to implement the approach

// Function to find the missing number
function findMissing(arr,N){
  let i;
  let temp = [];
  for (i = 0; i <= N; i++) {
            temp[i] = 0;
        }

        for (i = 0; i < N; i++) {
            temp[arr[i] - 1] = 1;
        }

        let ans = 0;
        for (i = 0; i <= N; i++) {
            if (temp[i] == 0)
                ans = i + 1;
        }
        console.log(ans);
}

// Driver code
        let arr = [ 1, 3, 7, 5, 6, 2 ];
        let n = arr.length;

        // Function call
       findMissing(arr,n);

4

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

Approach 2 – Using Summation Formula: O(n) time and O(1) space

The sum of the first N natural numbers is given by the formula N * (N + 1) / 2. Compute this sum and subtract the sum of all elements in the array from it to get the missing number.

Steps:

• Calculate the sum of the first N natural numbers using the formula: total_sum = N * (N + 1) / 2.
• Compute the sum of all elements in the array is array_sum.
• The missing number is total_sum - array_sum.

Implementation:

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

int getMissingNo(int arr[], int n)
{
    int N = n + 1; // The range is [1, N]
    int total_sum = N * (N + 1) / 2;

    // Sum of elements in the array
    int array_sum = accumulate(arr, arr + n, 0);

    // The missing number
    return total_sum - array_sum;
}

// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << getMissingNo(arr, N);
    return 0;
}

public class MissingNumber {

    // Function to get the missing number
    public static int getMissingNo(int[] arr, int n)
    {
        int N = n + 1; // The range is [1, N]
        int totalSum = N * (N + 1) / 2;

        // Sum of elements in the array
        int arraySum = 0;
        for (int num : arr) {
            arraySum += num;
        }

        // The missing number
        return totalSum - arraySum;
    }

    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 5 };
        int N = arr.length;
        System.out.println(getMissingNo(arr, N));
    }
}

def get_missing_no(arr, n):

    N = n + 1  # The range is [1, N]
    total_sum = N * (N + 1) // 2  # Calculate the sum of the range

    # Sum of elements in the array
    array_sum = sum(arr)

    # The missing number
    return total_sum - array_sum


# Driver code
arr = [1, 2, 3, 5]
N = len(arr)
print(get_missing_no(arr, N))

using System;

public class MissingNumber {
    // Function to get the missing number
    public static int GetMissingNo(int[] arr, int n)
    {
        int N = n + 1; // The range is [1, N]
        int totalSum = N * (N + 1) / 2;

        // Sum of elements in the array
        int arraySum = 0;
        for (int i = 0; i < n; i++) {
            arraySum += arr[i];
        }

        // The missing number
        return totalSum - arraySum;
    }

    public static void Main(string[] args)
    {
        int[] arr = { 1, 2, 3, 5 };
        int N = arr.Length;
        Console.WriteLine(GetMissingNo(arr, N));
    }
}

function getMissingNo(arr, n) {
    // The range is [1, N]
    const N = n + 1;
    // Calculate the sum of the range
    const totalSum = (N * (N + 1)) / 2;

    // Sum of elements in the array
    let arraySum = 0;
    for (let i = 0; i < n; i++) {
        arraySum += arr[i];
    }

    // The missing number
    return totalSum - arraySum;
}

// Driver code
const arr = [1, 2, 3, 5];
const N = arr.length;
console.log(getMissingNo(arr, N));

4

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

Approach 3 – Using XOR Operation: O(n) time and O(1) space

The XOR operation has useful properties for this problem. XOR of a number with itself is 0, and XOR of a number with 0 is the number itself. Using these properties, XOR all numbers in the range [1, N] and XOR all elements of the array. The result will be the missing number.

Steps:

• Initialize two variables x1 and x2 to 0.
• XOR all numbers from 1 to N and store the result in x1.
• XOR all elements of the array and store the result in x2.
• The missing number is x1 ^ x2.

Implementation:

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

// Function to get the missing number
int getMissingNo(int a[], int n)
{
    // For xor of all the elements in array
    int x1 = a[0];

    // For xor of all the elements from 1 to n+1
    int x2 = 1;

    for (int i = 1; i < n; i++)
        x1 = x1 ^ a[i];

    for (int i = 2; i <= n + 1; i++)
        x2 = x2 ^ i;

    return (x1 ^ x2);
}

// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
  
    // Function call
    int miss = getMissingNo(arr, N);
    cout << miss;
    return 0;
}

#include <stdio.h>

// Function to find the missing number
int getMissingNo(int a[], int n)
{
    int i;

    // For xor of all the elements in array
    int x1 = a[0];

    // For xor of all the elements from 1 to n+1
    int x2 = 1;

    for (i = 1; i < n; i++)
        x1 = x1 ^ a[i];

    for (i = 2; i <= n + 1; i++)
        x2 = x2 ^ i;

    return (x1 ^ x2);
}

// Driver code
void main()
{
    int arr[] = { 1, 2, 3, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);

    // Function call
    int miss = getMissingNo(arr, N);
    printf("%d", miss);
}

// Java program to find missing Number
// using xor

class Main {

    // Function to find missing number
    static int getMissingNo(int a[], int n)
    {
        int x1 = a[0];
        int x2 = 1;

        // For xor of all the elements in array
        for (int i = 1; i < n; i++)
            x1 = x1 ^ a[i];

        // For xor of all the elements from 1 to n+1
        for (int i = 2; i <= n + 1; i++)
            x2 = x2 ^ i;

        return (x1 ^ x2);
    }

    // Driver code
    public static void main(String args[])
    {
        int arr[] = { 1, 2, 3, 5 };
        int N = arr.length;

        // Function call
        int miss = getMissingNo(arr, N);
        System.out.println(miss);
    }
}

# Python3 program to find
# the missing Number
# getMissingNo takes list as argument


def getMissingNo(a, n):
    x1 = a[0]
    x2 = 1

    for i in range(1, n):
        x1 = x1 ^ a[i]

    for i in range(2, n + 2):
        x2 = x2 ^ i

    return x1 ^ x2


# Driver program to test above function
if __name__ == '__main__':

    arr = [1, 2, 3, 5]
    N = len(arr)

    # Driver code
    miss = getMissingNo(arr, N)
    print(miss)

# This code is contributed by Yatin Gupta

// C# program to find missing Number
// using xor
using System;

class GFG {
    // Function to find missing number
    static int getMissingNo(int[] a, int n)
    {
        int x1 = a[0];
        int x2 = 1;

        // For xor of all the elements in array
        for (int i = 1; i < n; i++)
            x1 = x1 ^ a[i];

        // For xor of all the elements from 1 to n+1
        for (int i = 2; i <= n + 1; i++)
            x2 = x2 ^ i;

        return (x1 ^ x2);
    }

    // Driver code
    public static void Main()
    {
        int[] arr = { 1, 2, 3, 5 };
        int N = 4;
      
        // Function call
        int miss = getMissingNo(arr, N);
        Console.Write(miss);
    }
}

// This code is contributed by Sam007_

      // Function to get the missing number
      function getMissingNo(a, n)
      {
      
        // For xor of all the elements in array
        var x1 = a[0];

        // For xor of all the elements from 1 to n+1
        var x2 = 1;
        for (var i = 1; i < n; i++) x1 = x1 ^ a[i];
        for (var i = 2; i <= n + 1; i++) x2 = x2 ^ i;

        return x1 ^ x2;
      }

      // Driver Code

      var arr = [1, 2, 3, 5];
      var N = arr.length;
      var miss = getMissingNo(arr, N);
      console.log(miss);
      
      // This code is contributed by rdtank.

<?php
// PHP program to find
// the Missing Number
// getMissingNo takes array and 
// size of array as arguments
function getMissingNo($a, $n)
{
    // For xor of all the
    // elements in array 
    $x1 = $a[0]; 
    
    // For xor of all the 
    // elements from 1 to n + 1
    $x2 = 1; 
    
    for ($i = 1; $i < $n; $i++)
        $x1 = $x1 ^ $a[$i];
            
    for ($i = 2; $i <= $n + 1; $i++)
        $x2 = $x2 ^ $i;     
    
    return ($x1 ^ $x2);
}

// Driver Code
$arr = array(1, 2, 3, 5);
$N = 4;
$miss = getMissingNo($arr, $N);
echo($miss);

// This code is contributed by Ajit.
?>

4

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

GeeksforGeeks

Improve