tanmay.vartak
BAN USERpublic class NextSparseNumber {
public static int getNextSparseNumber(int n) throws Exception {
if (n == Integer.MAX_VALUE) {
throw new Exception("Overflow");
}
int next = n + 1;
String binary = Integer.toBinaryString(next);
int currentLength = 0;
StringBuilder sparse = new StringBuilder();
for(int i = binary.length() - 1; i >=0; i--) {
if (binary.charAt(i) == '1') {
currentLength++;
continue;
}
if (currentLength == 0) {
sparse.append('0');
} else if (currentLength == 1) {
sparse.append('1');
sparse.append('0');
currentLength = 0;
} else {
while(currentLength > 0) {
sparse.append('0');
currentLength--;
}
currentLength = 1;
}
}
if(currentLength == 1) {
sparse.append('1');
} else {
//Need extra bit for next integer. So return 2^length of binary
if (binary.length() == 32) {
throw new Exception("Overflow");
}
return (int) Math.pow(2, binary.length());
}
return Integer.parseInt(sparse.reverse().toString(), 2);
}
public static void main(String[] args) throws Exception {
int n = 1;
while (n <= 128) {
System.out.println(n + " = " + Integer.toBinaryString(n));
n = NextSparseNumber.getNextSparseNumber(n);
}
}
}
- tanmay.vartak April 07, 2015
You can use quick sort to sort the array but during sorting if you need to do more than one swap just return false. Use pivot = N /2
- tanmay.vartak April 22, 2015This way you don't need additional space and most of the time don't need to sort entire array.