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.
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)/22. 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.