How to Find Missing Number on Integer Array of 1 to 100?

Question

Here is what i did. What can i do further? Can anybody suggest? I am looking for bitset solution.

public static void main(String args[]) {
// one missing number
printMissingNumber(new int[]{1, 2, 3, 4, 6}, 6);
// two missing number
printMissingNumber(new int[]{1, 2, 3, 4, 6, 7, 9, 8, 10}, 10);
// three missing number
printMissingNumber(new int[]{1, 2, 3, 4, 6, 9, 8}, 10);
// four missing number
printMissingNumber(new int[]{1, 2, 3, 4, 9, 8}, 10);
 // Only one missing number in array
int[] iArray = new int[]{1, 2, 3, 5};
int missing = getMissingNumber(iArray, 5);
System.out.printf("Missing number in array %s is %d %n", 
Arrays.toString(iArray), missing);

}

• Ravi K Thapliyal: Where's your implementation?

Answer 1

For n sequential numbers, the sum s = n(n+1)/2.

Sum up the numbers in the array and subtract it from s to find the missing number.

• Bathsheba: Plus one, exactly my answer and earlier.

Answer 2

If n is the largest number, and there is only one missing, then the missing number is

n * (n + 1) / 2 - sum{elements in your array}

The first term is the sum of n consecutive integers from 1 to, and including, n.

• ControlAltDel: He was asking about the bitset solution
• Bathsheba: Which is a terrible idea.
• ControlAltDel: terrible is a little strong :)
• Bathsheba: Yes, you have a point. There does exist an O(log N) solution, whereas mine is O(N) due to the array sum. So my answer is not as impeccable as I originally thought.