Find the missing number in an Array in Java with Examples

One of the most frequently asked basic java coding question is to find the missing number in an array of integers of length n-1 containing integer values from 1 to n.The given Array does not contain duplicates or occurrence of each integer value is only once.

I have faced this question for the java developer position twice. Make sure this question in your to do list before appearing for the interview.

There are follow up questions like
  • how to find the missing number in a given unsorted array with duplicates.If you solve it, then another follow up question is
  • find the multiple missing numbers in a given unsorted array with duplicates.
Below is the java code for each of the above questions.

Read Also :   How to Reverse a String in java


Examples :

int[] input = {10,9,6,7,4,3,5,1,2}

Output : 
Missing number in an array : 8



int[] input = {6,1,4,2,3}

Output :
Missing number in an array : 5

Solution

1. First step, we will find the sum of n numbers using math formula n*(n+1)/2

2. Second step, we will find the sum of all numbers in the given input array.

3. Using subtraction, we will find the missing number

 missingNumber = (Sum of 1 to n numbers) - (Sum of numbers in the given input array)

Java Program to find the missing number in an Array, Duplicates not allowed :

Below is the java program to find the missing number in an Array, Duplicates are not allowed.

/* Java Program to find the 
missing number in a given unsorted array 
duplicates are not allowed */

public class JavaHungry {
    
    public static void main(String args[]) {
        
        // Given input Array from 1 to n 
        int[] input = {10,9,6,7,4,3,5,1,2}; 
 
        // Calculate n value  
        int n = input.length + 1;
 
        // Calculate Sum of N Number 
        // using Math formula n(n+1)/2 
        int sumOfNNumbers = sumOfAllNNumbers(n);
        
        // Calculate Sum of all numbers in input array
        int sumOfInputArray = sumOfInputArrayNumbers(input);
        
        // Calculate missing number
        // using subtraction
        int missingNumber = sumOfNNumbers - sumOfInputArray; 
 
        // Print the Missing number          
        System.out.println("Missing number in an array is : " 
                                            + missingNumber);
    }
    
    public static int sumOfAllNNumbers(int n){
        int sum = (n*(n+1))/2;
        return sum;
    }
    
    public static int sumOfInputArrayNumbers(int[] input){
        int sum = 0;
        for(int i=0; i < input.length ;i++){
            sum = sum + input[i];
        }
        return sum;
    }
}

Output :
Missing number in an array is : 8

Follow up question :

How to find the missing number in an unsorted Array with duplicate elements.

Examples :

Integer[] input = {10,9,6,7,7,9,10,3,4,3,5,1,2}

Output : 
Missing number in an array : 8


Integer[] input = {6,1,4,2,3,3,1,6}

Output :
Missing number in an array : 5

Solution :

1. First Step, convert the given input Array to List and pass this List to the HashSet constructor. Using this step I remove the duplicate elements from the List. Rest is same as the previous question.

Java Program to find the missing number in an unsorted Array with duplicates allowed :

Below is the java program to find the missing number in an unsorted Array with Duplicates allowed.

/* Java Program to find the 
missing number in a given unsorted array
with duplicates allowed */

import java.util.*;

public class JavaHungry {
    
    public static void main(String args[]) {

        // Given input Array from 1 to n 
        Integer[] input = {10,9,6,7,7,9,10,3,4,3,5,1,2};
        
        
        //Convert input Array to List
        List arrList = Arrays.asList(input);
        
        //Remove Duplicates by passing list
        //to the HashSet Constructor
        HashSet<Integer> hsobj = new HashSet(arrList);

        // Calculate n value  
        int n = hsobj.size() + 1;
        
        // Calculate Sum of N Number 
        // using Math formula n(n+1)/2 
        int sumOfNNumbers = sumOfAllNNumbers(n);
        
        // Calculate Sum of all numbers in HashSet object
        int sumOfHashSetNumbers = sumOfHashSetNumbers(hsobj);
        
        // Calculate missing number
        // using subtraction
        int missingNumber = sumOfNNumbers - sumOfHashSetNumbers; 
 
        // Print the Missing number 
        System.out.println("Missing number in an array is : " 
                                            + missingNumber);
    }
    
    public static int sumOfAllNNumbers(int n){
        int sum = (n*(n+1))/2;
        return sum;
    }
    
    public static int sumOfHashSetNumbers(HashSet<Integer> hsobj){
        int sum = 0;
        for(Integer obj : hsobj){
            sum = sum + obj;
        }
        return sum;
    }
}

Output :
Missing number in an array is : 8


Follow up question :

How to find the multiple missing numbers in an unsorted Array with duplicate elements.

Examples :

int[] input = {10,9,6,7,7,5,1,2,2}

Output : 
Missing numbers in an array are : 3 4 8


int[] input = {6,1,3,3,1,6,8}

Output :
Missing numbers in an array are : 2 4 5 7

Solution :

1. Create another Array named as copyArray of the given input Array. Mark all the indexes present in the copyArray to 1 for the corresponding value in input Array.
2. Calculate the max value in the given input Array.We will iterate copyArray till max value while printing the missing numbers.
3. Iterate through the copyArray and print all those values which are 0. Hence, the missing numbers.

Java Program to find the multiple missing numbers in an unsorted Array with duplicates allowed:


/* Java Program to find multiple 
missing numbers in a given unsorted 
array with duplicates allowed */

import java.util.*;

public class JavaHungry {
    
    public static void main(String args[]) {

        // Given input Array from 1 to n 
        Integer[] input = {6,1,3,3,1,6,8};
        
        // Calculate the max value in given Array
        int max = calculateArrayMaxValue(input);

        //Create another Array of same size 
        //By default all values initialize to 0
        // default value of int 
        int[] copyArray = new int[100];
        
        //Iterate thorugh the input array
        //Mark all present numbers in copyArray
        for(int i : input) {
            copyArray[i] = 1;
        }
        
        
        // Print the missing numbers
        System.out.print("Missing numbers in an array are : "); 
        
        for(int i=1 ;i <= max; i++){
            if(copyArray[i]==0)
                System.out.print(i + " ");
        }
    }
    
    public static int calculateArrayMaxValue(Integer[] input) {
    
        // Initialize maximum element 
        int max = input[0]; 
        
        // Iterating array elements from second and 
        // compare every element with current max   
        for (int i = 1; i < input.length; i++) 
            if (input[i] > max) 
                max = input[i]; 
        
        return max; 
        
    }
}

Output :
Missing numbers in an array are : 2 4 5 7

Above, I have demonstrated how to find the missing number in an Array. Also, find the missing number in an unsorted Array when duplicates are allowed and find the multiple missing numbers when duplicates are allowed.

Please share your own version of java code for the above programs in the comment section.

About The Author

Subham Mittal has worked in Oracle for 3 years.
Enjoyed this post? Never miss out on future posts by subscribing JavaHungry