Skip to content

Instantly share code, notes, and snippets.

@bchetty
Created May 24, 2013 20:45
Show Gist options
  • Save bchetty/5646399 to your computer and use it in GitHub Desktop.
Save bchetty/5646399 to your computer and use it in GitHub Desktop.
Missing Number's problem.
public class MissingNumbers {
public static void main(String[] args) {
//In the below code: Array Size = 8 and n = 10.
//So 2 missing numbers!
int n = 10;
int[] intArr = new int[] {3,1,2,5,4,7,10,8};
MissingNumbers missingNums = new MissingNumbers();
int[] missingNums = missingNums.findMissingNumber(intArr, n);
for(int i=0;i<missingNums.length;i++) {
System.out.println("Missing Number " + (i + 1) + " : " + missingNums[i] + " ");
}
}
private int[] findMissingNumber(int[] intArray, int totalNum) {
int numOfMissingNums = totalNum - intArray.length;
BitSet bitSet = new BitSet(totalNum);
for(int i: intArray) {
bitSet.set(i-1);
}
int[] missingNums = new int[numOfMissingNums];
for(int k=0;k<numOfMissingNums;k++) {
int index = (k == 0) ? 0 : (missingNums[k - 1]);
missingNums[k] = (bitSet.nextClearBit(index) + 1);
}
return missingNums;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment