Saturday, March 3, 2012

Find missing number in a list in java

Problem :- 

         Assume that there is a list of numbers that has numbers from 1 to n. Out of the list, one number is missing. Find the missing number from the list.

Solution :-

       The solution (written in java) with least time complexity is to use BitSet and set bit in the bitset for each corresponding number in the list. The first bit that is not set will be the missing number in the list.

void findMissingNum(int[] ar) {
if(ar != null) {
BitSet bs = new BitSet(ar.length);
for(int no : ar) {
System.out.println("Missing number=" + bs.nextClearBit(1));