Java Program To Identify the Missing Number in a given Array

In this tutorial, we will learn how to identify the missing elements in an array. This means we have to find that one missing element in the list of n-1 integers where integers are in the range of 1 to n and there are no duplicates in the list. But before moving forward, if you are not familiar with the concepts of the array, then do check the article Arrays in Java.

Input: 1 2 4 5 6

Output: Missing Element is 3.

Program 1: Find Missing Element Using Total Sum Technique

In this program, we will see how to identify the missing element in the array using the total sum technique. The logic behind this approach is that first we find the total sum of all the elements in the array by using the formula sum=(n+1)*(n+2)/2. Here, we are using the formula sum=(n+1)*(n+2)/2 instead of sum=(n)*(n+1)/2 because the total number of elements here is n but as one element is missing so the total number adds up to n+1.

Algorithm

1. Start
2. Declare the array size.
3. Ask the user to initialize the array size.
4. Declare the array.
5. Ask the user to initialize the array elements.
6. Calculate the sum of first n natural numbers using a formula as sumtotal= n*(n+1)/2
7. Declare a variable sum to store the sum of array elements.
8. Using a for loop traverse through each element of the array.
9. Deduct each element from the total sum calculated.
10. The remaining element in the sum will be the missing element.
11. Print the sum.
12. Stop.

The below program demonstrates how to identify the missing element in the array using the total sum technique.

/*Java Program to find the missing element*/
import java.util.*;  
import java.util.Arrays; 

//Driver Code
public class Main  
{  
   public static void main(String args[])   
   {  
       Scanner sc=new Scanner(System.in);

      int n;    //Declare array size
      System.out.println("Enter the total number of elements ");
      n=sc.nextInt();     //Initialize array size

      int arr[]=new int[n];   //Declare array
      System.out.println("Enter the elements of the array ");
      for(int i=0; i<n ;i++)     //Initialize array
      {
          arr[i]=sc.nextInt();
      }
      
      int sum=(n+1)*(n+2)/2;   //Calculate the expected sum of all the elements from 1 to n
      for(int i=0;i<n;i++)
      {
          sum=sum-arr[i]; //Subtract each element from the sum
      }
      System.out.println("Missing Element is "+sum);  //Print the missing element
   }
}

Enter the total number of elements 4
Enter the elements of the array 1 2 4 5
Missing Element is 3

Program 2: Find the Missing Element Using XOR Technique

In this program, we will see how to identify the missing element in an array using XOR Technique.

Algorithm

1. Start
2. Declare the array size.
3. Ask the user to initialize the array size.
4. Declare the array.
5. Ask the user to initialize the array elements.
6. Declare two variables. Initialize the first variable to the first element of the array and the second variable to 1.
7. Use a for loop to iterate through all the elements.
8. Find the XOR of each element with the first variable.
9. Use another for loop to iterate through all the elements.
10. Find the XOR of each element with the second variable.
11. The missing element is found by taking the XOR of the above-resulting variables.
12. Print the missing element.
13. Stop.

The below program demonstrates how to identify the missing element in the array using XOR Technique.

/*Java Program to find the missing element*/
import java.util.*;  
import java.util.Arrays; 
 
//Driver Code
public class Main  
{  
   public static void main(String args[])   
   {  
       Scanner sc=new Scanner(System.in);
 
      int n;    //Declare array size
      System.out.println("Enter the total number of elements ");
      n=sc.nextInt();     //Initialize array size
 
      int arr[]=new int[n];   //Declare array
      System.out.println("Enter the elements of the array ");
      for(int i=0; i<n ;i++)     //Initialize array
      {
          arr[i]=sc.nextInt();
      }
      
        int x1 = arr[0];
        int x2 = 1;
 
        /* For xor of all the elements in array */
        for (int i = 1; i < n; i++)
            x1 = x1 ^ arr[i];
 
        /* For xor of all the elements  from 1 to n+1 */
        for (int i = 2; i <= n + 1; i++) 
        {
            x2 = x2 ^ i;
        }
        int melement=x1 ^ x2;
        System.out.println("Missing Element is "+melement);  //Print the missing element
   }
}

Enter the total number of elements 7
Enter the elements of the array 1 2 3 4 5 7 8
Missing Element is 6