Java Program to Find the Missing Element in an Integer Array

«
»

This is the Java Program to Find the Missing Element in an Integer Array.

Problem Description

Given an array of n-1 integers having no duplicates, and containing the integers in the range 1 to n.
Find out the missing integer.
Example:
Array = [ 1, 2, 4, 5]

advertisement

Output :
Missing integer = 3

Problem Solution

Take two variables to say x and y, in x store the XOR of all array elements and in y store the XOR of integers from 1 to n. Finally, take the result of XOR of x and y, this result is our missing integer.

Program/Source Code

Here is the source code of the Java Program to Find the Missing Element in an Integer Array. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

advertisement
advertisement
  1.  
  2. //Java Program to Find the Missing Element in an Integer Array.
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6.  
  7. public class MissingInteger {
  8.     // Function to calculate XOR values and return the missing integer.
  9.     static int findMissingInteger(int[] array){
  10.         int i;
  11.         int XOR1, XOR2;
  12.         XOR1 = array[0];
  13.         XOR2 = 1;
  14.         for(i=1;i<array.length;i++){
  15.             XOR1 ^= array[i];
  16.             XOR2 ^= (i+1);
  17.         }
  18.         XOR2 ^=(i+1);
  19.         return (XOR2 ^ XOR1);
  20.     }
  21.     // Function to read the input and display the output
  22.     public static void main(String[] args) {
  23.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  24.         int size;
  25.         System.out.println("Enter the range of the values (starts from 1)");
  26.         try {
  27.             size = Integer.parseInt(br.readLine());
  28.         } catch (Exception e) {
  29.             System.out.println("Invalid Input");
  30.             return;
  31.         }
  32.         int[] array = new int[size-1];
  33.         System.out.println("Enter array elements");
  34.         int i;
  35.         for (i = 0; i < array.length; i++) {
  36.             try {
  37.                 array[i] = Integer.parseInt(br.readLine());
  38.             } catch (Exception e) {
  39.                 System.out.println("An error occurred");
  40.                 return;
  41.             }
  42.         }
  43.         int missing = findMissingInteger(array);
  44.         System.out.println("The missing integer is " + missing);
  45.     }
  46. }
Program Explanation

1. The function findMissingInteger(), initializes the variables XOR1 to array[0] and XOR2 to 1.
2. The loop for(i=1; i<array.length; i++) is used to iterate through the array and store the XOR of its elements in XOR1 and XOR of first n-1 integers in XOR2.
3. The statement XOR2^=(i+1) XOR’s the integer n.
4. The statement (XOR1^XOR2) returns the missing integers.

Time Complexity: O(n) where n is the number of elements in the array.

Runtime Test Cases
advertisement
 
Case 1 (Simple Test Case):
 
Enter the range of the values (starts from 1)
5
Enter array elements
1
2
4
5
The missing integer is 3
 
Case 2 (Simple Test Case - another example):
 
Enter the range of the values (starts from 1)
8
Enter array elements
8
7
6
5
4
3
2
The missing integer is 1

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.