How to Find Missing Number on Integer Array of 1 to 100 - BitSet Example (original) (raw)

One of the most frequently asked questions on programming interviews are, write a program to find the 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 technology companies like Google, Amazon, Facebook, Microsoft, mostly when they visit the campus of reputed universities to hire graduates. The simplest version of this question is to find missing elements in an area of 100 integers, which contains numbers between 1 and 100.

If it has more than one missing element that you can use BitSet class, of course only if your interviewer allows it.

Sum of the series: Formula: n (n+1)/2( but only work for one missing number)
Use BitSet, if an array has more than one missing element.

I have provided a 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 a nice way to learn how to use BitSet in Java as well.

By the way, if you are going for interview, then apart from this question, its also good to know how to find duplicate numbers 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.

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

You can see that how using the right data structure can solve the problem easily. This is the key takeaway of this program, for the more coding question, you can check these coding interview courses and the classic coding interview book, Cracking the Coding Interviews, a collection of 189 coding questions from programming interviews of tech companies like Google, Amazon, Microsoft, and others.

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, you can also check here.