How to Find Missing Number on Integer Array of 1 to 100 - BitSet Example

By: Khondoker Hafizur Rahman on 2:31 AM

One of the most frequently asked
question on programming interviews is, write a program to find missing number
in an array in Java, C# or any other language; depending upon which language
you choose. This kind of coding interview questions are not only asked in
small start-ups but also on some of the biggest technical companies like
Google, Amazon, Facebook, Microsoft, mostly when they visit campus of reputed
universities to hire graduates. Simplest version of this question is to find
missing elements in an area of 100 integers, which contains numbers between
1 and 100. This can easily be solved by calculating sum of the series using n(n+1)/2, and this is also one of the quickest and efficient way,
but it cannot be used if array contains more than one missing numbers or if
array contains duplicates. This gives interviewer some nice follow-up questions
to check whether candidate can apply his knowledge on slightly different condition
or not. So if you get through this, they will ask you to find missing number in
array of duplicates. This might be tricky but you will soon find out that
another way to find find missing and duplicate number in array is to sort it.
In sorted array, you can compare whether a number is equal to expected next
number or not. Alternatively you can also use BitSet in Java to solve this problem. By the way, if you are going
for interview, then apart from this question, its also good to know how to find duplicate number in array and program to find second highest number in an integer array.
More often than not, those are asked as follow-up question after this.

Java Program to find missing numbers

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? If Interviewer especially mention
1 to 100 then you can apply the above trick about sum of the series, as shown
below as well. If it has more than one missing element than you can use BitSet class, of-course only if your interviewer allows it.



1) Sum of the series : Formula : n (n+1)/2( but only work for one missing
number)

2) Use BitSet, if array has more than one missing
elements.



I have provided BitSet
solution with another
purpose, to introduce with this nice utility class. In many interviews I have
asked about this class to Java developers, but many of them not even aware of
this. I think this problem is nice way to learn how to use BitSet in Java as well.

import java.util.Arrays;

import java.util.BitSet;

/**

 * Java program to find missing elements in a
Integer array containing 

 * numbers from 1 to 100.

 *

 * @author Javin Paul

 */

public class MissingNumberInArray {

    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);

    }

   /**

    * A general method to find missing values
from an integer array in Java.

    * This method will work even if array has
more than one missing element.

    */

    private static void printMissingNumber(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("Missing 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.println(++lastMissingIndex);

        }

    }

   /**

    * Java method to find missing number in
array of size n containing

    * numbers from 1 to n only.

    * can be used to find missing elements on
integer array of 

    * numbers from 1 to 100 or 1 - 1000

    */

    private static int getMissingNumber(int[] numbers, int totalCount) {

        int expectedSum = totalCount * ((totalCount + 1) / 2);

        int actualSum = 0;

        for (int i : numbers) {

            actualSum += i;

        }

        return expectedSum - actualSum;

    }

}

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

Missing number in array [1, 2, 3, 5] is 4

That's all on this program to find missing element in an array of 100
elements. As I said, it's good to know the trick, which just require you to
calculate sum of numbers and then subtract that from actual sum, but you can
not use that if array has more than one missing numbers. On the other hand, BitSet solution is more general, as you can use it to find more
than one missing values on integer array. For more programming questions,