A commonly asked puzzle at Java interviews is – find the missing number from a series or array of numbers. This puzzle has been asked in Amazon.com.
In this Java puzzle, you have a series of numbers start (e.g. 1….N) and exactly one number in this series is missing. You have to write a java program to find missing number from series.
Solution to find mising number
Surprisingly, solution of this puzzle is very simple only if you know it already.
- Calculate
A = n (n+1)/2where n is largest number in series 1…N. - Calculate B = Sum of all numbers in given series
- Missing number = A – B
Let’s a write the solution in code.
public class FindMissingNumber {
public static void main(String[] args) {
//10 is missing
int[] numbers = {1,2,3,4,5,6,7,8,9, 11,12};
int N = 12;
int idealSum = (N * (N + 1)) / 2;
int sum = calculateSum(numbers);
int missingNumber = idealSum - sum;
System.out.println(missingNumber);
}
private static int calculateSum(int[] numbers) {
int sum = 0;
for (int n : numbers) {
sum += n;
}
return sum;
}
}
Output:
10
Solution to find mising number – Java 8
Above code, though simple, can be reduced by many lines using new language features such as lambda in Java 8. Let’s see how?
import java.util.Arrays;
public class FindMissingNumber {
public static void main(String[] args) {
//10 is missing
int[] numbers = {1,2,3,4,5,6,7,8,9, 11,12};
int N = 12;
int idealSum = (N * (N + 1)) / 2;
int sum = Arrays.stream(numbers).sum();
int missingNumber = idealSum - sum;
System.out.println(missingNumber);
}
}
Output:
10
Puzzles like these are simple to solve, but it is always useful to know the solution before it is asked in any interview. So be ready to find missing number in array, in your next interview.
Happy Learning !!
Reference: SO Thread
it’s better to replace add with xor, never overflow
Right! Was my first thought when I tried to do it myself. It will take constant space. To get XOR for given range next solution can be used
https://www.geeksforgeeks.org/find-xor-of-numbers-from-the-range-l-r/
But i just iterate full list and it doesn’t affect existing complexitty O(n), here is the code:
List nums = List.of(5, 10, 6, 4, 1, 3, 9, 8, 2);
int xorForFullList = 0;
for (int i = 0; i < nums.size() + 1; i++) {
xorForFullList ^= i + 1;
}
int xorForGivenList = 0;
for (Integer num : nums) {
xorForGivenList ^= num;
}
int missingNum = xorForFullList ^ xorForGivenList;
System.out.println("missingNum=" + missingNum);
how to find multiple numbers missing in a sequence using java 8 streams?
why he is taken N=12 only
It is the largest number in series.
How is it coded if there are more numbers like 1 to 200?