Find the Missing Number

Problem Statement

In finding the missing number from an array of 1 to N numbers we have given an array that contains N-1 numbers. One number is missing from an array of numbers from 1 to N. We have to find the missing number.

Input Format

First-line containing an integer N.

Second-line containing N-1 integers.

Output Format

In a single line print the missing number.

Constraints

• 2<=N<=100000
• 1<=a[i]<=N

Approach 1 for Find the Missing Number 

We use the Simple Mathematics formula as shown in the below algorithm.

Algorithm

1. We know the sum of numbers from 1 to N is given by the formula N*(N+1)/2. Let us call this as real_sum.

2. And then we sum the elements present in the array and let us call it missing_sum.

3. Simple the difference between real_sum and missing_sum is the missing number as it was not added while computing the missing_sum.

Implementation for Find the Missing Number 

C++ Program 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n-1];
  for(int i=0;i<n-1;i++)
  {
      cin>>a[i];
  }
  // sum1 store the sum of 1 to N numbers which is N*(N+1)/2;
  ll sum1=(n*(n+1))/2;
  ll sum2=0;
  for(int i=0;i<n-1;i++)
  {
    //sum of elements present in the array;  
    sum2+=a[i]; 
  }
  cout<<"Missing number is: "<<sum1-sum2<<endl;
  return 0;
}

Java Program 

import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n-1];
        for(int i=0;i<n-1;i++)
        {
            arr[i] = sr.nextInt();
        }
        // sum1 store the sum of 1 to N numbers which is N*(N+1)/2;
        int sum1=(n*(n+1))/2;
        int sum2=0;
        for(int i=0;i<n-1;i++)
        {
          //sum of elements present in the array;  
          sum2+=arr[i]; 
        }
        System.out.println("Missing number is: "+(sum1-sum2));
    }
}

7
1 2 3 4 5 7

Missing number is: 6

Complexity Analysis for Find the Missing Number

Time Complexity

O(N) where N is the given value in the first line of input. Here we iterate the given array for finding the sum of elements.

Space Complexity

O(1) because we don’t use any auxiliary space here. Just use some variables to store the sum.

Approach 2 for Find the Missing Number 

We use the concept of XOR operation.

As we know,

A xor A = 0   ————- Property 1

i.e. xor of 2 similar elements is zero.

Also,

A xor 0 = A   ————- Property 2

i.e. xor of any element with zero gives the same number.

Algorithm

1. We compute the XOR of all the values from 1 to N and say it is X.

2. We compute the XOR of all the values in the array and say it is Y.

3. Now when we do (X xor Y) we basically are XORing all values twice except the missing number which came only once. Thus the final value is nothing but the missing number by property 2 of XOR.

Implementation for Find the Missing Number 

C++ Program 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n-1];
  for(int i=0;i<n-1;i++)
  {
      cin>>a[i];
  }
  int X = 0,Y = 0;
  for(int i=1;i<=n;i++)
  {
      //XOR of all elements from 1 to N
      X^=i;
  }
  for(int i=0;i<n-1;i++)
  {
      //XOR of all elements in the array
      Y^=a[i]; 
  }
  int missing_Num=X^Y;
  cout<<"Missing number is: "<<missing_Num<<endl;
  return 0;
}

import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n-1];
        for(int i=0;i<n-1;i++)
        {
            arr[i] = sr.nextInt();
        }
        int X = 0,Y = 0;
        for(int i=1;i<=n;i++)
        {
            //XOR of all elements from 1 to N
            X^=i;
        }
        for(int i=0;i<n-1;i++)
        {
            //XOR of all elements in the array
            Y^=arr[i]; 
        }
        int missing_Num=X^Y;
        System.out.println("Missing number is: "+missing_Num);
    }
}

9
1 2 3 4 6 7 8 9

Missing number is: 5