praneeth.gayam
BAN USERYour answer for 1010 is not correct. While 10100 is sparse int, it is not next sparse int. 10000 would be the next sparse int.
- praneeth.gayam May 22, 2015Time Complexity:O(log n)
Space Complexity:O(log n) solution
Works for non-negative integers only.
int findNextSparseInt(int n) {
if (n < 0) return -1;
n++; //Even if n is sparse we should return next sparse int
Stack sourceStack = createStack();
int i = 0;
int checker = power(2, i);
while (true) {
while (checker <= n) {
checker = power(2, ++i);
}
sourceStack.push(i - 1);
n = n - power(2, i-1);
if (n == 0) break;
i = 0; checker = 1;
}
Stack destStack = createStack();
while (sourceStack.size > 0) {
if (destStack.size == 0) {
destStack.push(sourceStack.pop());
continue;
}
if (sourceStack.peek() - destStack.peek() < 2) {
destStack.clear();
destStack.push(sourceStack.pop() + 1);
} else {
destStack.push(sourceStack.pop());
}
}
int sparseInt = 0;
while (destStack.size > 0) {
sparseInt += getTwoPower(destStack.pop());
}
return sparseInt;
}
Repmonicahbess, SDET at Adap.tv
Hi Everyone, I'm Monica H. Bess. I love to build props...everything from a casket to pneumatic monsters.My ...
Returns result and remainder.
Time Complexity : O(logn)
- praneeth.gayam May 23, 2015