Let’s understand the problem statement, we have numbers from 1 to 100 that are put into an integer array, what’s the best way to find out which number is missing?
1) Sum of the series: Formula: n (n+1)/2( but only work for one missing number)
2) Use BitSet, if an array has more than one missing element.
import java.util.Arrays;
import java.util.BitSet;
public class temp{
private static void Missing_Number(int[] numbers, int count){
int missingCount = count - numbers.length;
BitSet bitSet = new BitSet(count);
for (int number : numbers){
bitSet.set(number - 1);
}
System.out.printf("\nMissing numbers in integer array %s, with total number %d is %n",Arrays.toString(numbers), count);
int lastMissingIndex = 0;
for (int i = 0; i < missingCount; i++) {
lastMissingIndex = bitSet.nextClearBit(lastMissingIndex);
System.out.printf(" %d \n",++lastMissingIndex);
}
}
public static void main(String args[]){
Missing_Number(new int[]{1, 2, 3, 4, 6}, 6);
Missing_Number(new int[]{1, 2, 3, 4, 6, 7, 9, 8, 10}, 10);
Missing_Number(new int[]{1, 2, 3, 4, 6, 9, 8}, 10);
Missing_Number(new int[]{1, 2, 3, 4, 9, 8}, 10);
}
}
Output:
Missing numbers in integer array [1, 2, 3, 4, 6], with total number 6 is
5
Missing numbers in integer array [1, 2, 3, 4, 6, 7, 9, 8, 10], with total number 10 is
5
Missing numbers in integer array [1, 2, 3, 4, 6, 9, 8], with total number 10 is
5
7
10
Missing numbers in integer array [1, 2, 3, 4, 9, 8], with total number 10 is
5
6
7
10
ScrShot
