## Amazon Interview Question for SDE-2s

• 4

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
6
of 8 vote

``````Not sure about sparse number but below code will give no adjacent 1. Can someone check

private static void nextSparse(int x) {
for (int i = x + 1; i < Integer.MAX_VALUE; i++) {
if ((i & (i * 2)) == 0) {
System.out.println(i);
return;
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Nice solution. But it's Brute Force approach, which may have high processing for certain inputs. For eg. Input - 10101010, Output :- 100000000, this approach will check each and every number from input to output, which may grow exponentially for very large inputs.

Comment hidden because of low score. Click to expand.
2
of 4 vote

There are 2 possible number types you are going to deal with:
2. non-sparse number

Algorithm for solution based on the 2 scenarios:

1. Check if binary representation of number is Sparse, if it is:

- Check if bin. number contains a sequence of at least 2 zeros: (i.e "xx1100xx" or "xx11001xx") this will enable for fitting a 1 just right at index of first 0 found and setting to 0 all the right remaining bits (i.e"1010010" to "1010100"). If index of first 2 zeros is 0, just return n+1, i.e"10100" to "10101").

-If it doesn't contain a seq. of 2 zeros
shift N left of 1 and set all remaining bits to 0,
return 1 << n (n = length of integer). *This is same as returning next higher power of 2.
i.e"10101", "100000")

2. If number is not sparse:

- Check for highest index of a sequence of at least 2 ones (i.e "10011010001" - index 6) then we will see if we can put a 1 at starting index after sequence and set remaining bits to zero on the right side. (i.e: "10011010001" to "10100000000")
If we find out we created a new seq. of 2 one's on that index (i.e: "10110010001" to "11000000000") then we keep flipping bits to 0 until we get to a point where previous bit is 0 and next is 1 (i.e "101xx") which is sparse, or 0.

- If we get 0 then we just need to left shift 1 by the original number's length, example: "110010010" to "1000000000" (512). - Next power of 2.

Implementation:

``````public class Solution {
public static void main(String args[]) {
int n = 72;
System.out.println(convertToBinaryString(n));
int nextSparse = getNextBiggerSparseNumber(n);
System.out.println(nextSparse);
System.out.println(convertToBinaryString(nextSparse));
}

public static int getNextBiggerSparseNumber(int n) {
if(isSparseBinaryNumber(n)) {
int i = getFirstIndexSeqZeros(n);
if (i != -1) {
if (i - 1 == 0) {
return n + 1;
}

return incrementToNextSparseFromZeroIndex(n, i - 1);

} else {
return 1 << getLengthBits(n);
}
} else {
int i = getLastIndexSeqOnes(n);
return incrementToNextSparseFromIndex(n, i);
}

}

/**
* Sets the bit at index to 1 while setting all remaining bits on the right to 0, "1001101" index 4 -> "1010000"
* @param n
* @param index
* @return
*/
public static int incrementToNextSparseFromZeroIndex(int n, int index) {
int i = index - 1;
int n2 = n;
n2 = setBit(n2, index, true);
while(i >= 0) {
n2 = setBit(n2, i, false);
i--;
}
return n2;
}

/**
* Sets all bits of n to 0 until index, from right to left, then sets next bit index+1 to 1 and checks next bit,
* if next is 1 or if number is lower than original n, keeps setting last bit to 0 and current to 1, from right
* to left until a valid condition for sparse number is reached, otherwise if it reaches 0 returns next power of
* 2. (1 << sizeOf(n))
*
* @param n
* @param index
* @return
*/
public static int incrementToNextSparseFromIndex(int n, int index) {
int i = 0;
int n2 = n;
boolean prev = false, current = false;

while(i <= index) {
n2 = setBit(n2, i, false);
i++;
}
n2 = setBit(n2,  i, true);
prev = true;
i++;
current = getBit(n2,  i);

while (current && prev && n2 > 0 || (n2 < n && n2 > 0)) {
n2 = setBit(n2, i - 1, false);
n2 = setBit(n2, i, true);
i++;
prev = current;
current = getBit(n2,  i);
}
if (n2 == 0) {
return 1 << getLengthBits(n);
}

return n2;
}

/**
* Checks index of first seq. of 2 consecutive zeros. i.e: "1001 -> index = 2"
* if no seq. found return -1
*
* @param n
* @return
*/
public static int getFirstIndexSeqZeros(int n) {
// current and previous bit if set to 0 then true
boolean cur, prev = false;

int i = 0;
while(n > 0) {
if ( (n & 1) == 0) {
cur = true;
} else {
cur = false;
}
if (cur && prev) {
return i;
}
prev = cur;

i++;
n = n >> 1;
}

return -1;
}

/**
* Checks index of last seq. of 2 consecutive 1. i.e: "1011001 -> index 3"
* if no seq. found return -1
*
* @param n
* @return
*/
public static int getLastIndexSeqOnes(int n) {
// current and previous bit if set to 1 then true
boolean cur, prev = false;

int i = 0;
int highest = -1;

while(n > 0) {
if ( (n & 1) == 1) {
cur = true;
} else {
cur = false;
}
if (cur && prev) {
highest = i;
}
prev = cur;

i++;
n = n >> 1;
}

return highest;
}

/**
* Checks if number is sparse: if 2 consecutive 1 are present.
* @param n
* @return
*/
public static boolean isSparseBinaryNumber(int n) {
// current and previous bit if set to 1 then true
boolean cur, prev = false;

while(n > 0) {
if ( (n & 1) == 1) {
cur = true;
} else {
cur = false;
}
if (cur && prev) {
return false;
}
prev = cur;

n = n >> 1;
}

return true;
}

public static int getLengthBits(int n) {
int count = 0;
while (n > 0) {
count++;
n = n >> 1;
}
return count;
}

public static String convertToBinaryString(int n) {
StringBuilder sb = new StringBuilder();

while(n > 0) {
if ( (n & 1) == 1) {
sb.append("1");
} else {
sb.append("0");
}

n = n >> 1;
}

return sb.reverse().toString();
}

public static boolean getBit(int n, int index) {
return ((n & (1 << index)) > 0);
}

public static int setBit(int n, int index, boolean b) {
if (b) {
return n | (1 << index);
} else {
return n & ~(1 << index);
}
}

}``````

Comment hidden because of low score. Click to expand.
0

"Check if it contains a sequence of at least 3 zeros in the middle (i.e "10010001") this will enable for fitting a 1 in the middle."

You cannot just put 1 in the middle to find next sparse number,
for example 10010010 is less than 10010101 and it is sparse.

Comment hidden because of low score. Click to expand.
0

"Check if it contains a sequence of at least 3 zeros in the middle (i.e "10010001") this will enable for fitting a 1 in the middle."

You cannot just put 1 in the middle to get next sparse number,
for example 10010010 is less than 10010101 but also sparse.

Comment hidden because of low score. Click to expand.
0

@madi.sagimbekov Thanks for your input, actually it's not a seq. of 3 zeros, but 2, we test by placing a 1 at first found zero, and keep iterating left to see if we still have adjacent ones, I updated the answer to handle this scenario now it works correctly please verify.

Comment hidden because of low score. Click to expand.
0

Maybe: put two zeros "00" in the front of the binary representation...

Comment hidden because of low score. Click to expand.
1
of 1 vote

@ninhnnsoc updated the answer with comments on each important method and wrote a better explanation of each scenario.

Comment hidden because of low score. Click to expand.
1
of 1 vote

public class NexBiggerSParseNum {
static String temp;

public static void main(String[] args) {
int num = 72;
int len;

for (int i= num+1; i < Integer.MAX_VALUE ; i++){
if(isSparseNum(i)){
System.out.println("Next Parse Num is "+i);
break;
}
}

}

public static boolean isSparseNum(int num){
temp = Integer.toBinaryString(num);
return temp.indexOf("11")>0?false:true;
}

}

Comment hidden because of low score. Click to expand.
0

10001 is sparse.But as per your algo, 100000 should be next sparse number , but I think 10101 is also a sparse and next one.

Comment hidden because of low score. Click to expand.
1
of 1 vote

It's simple, is O(log n), minimizes the number of ALU ops, and isn't constrained to 32-bit types (but will work - look to the 'n', 't' & return types).

``````public static long next( long n )
{
n++;

long t = 0;
int i = 0;

while( n > 0 )
{
if( (n&0b11) == 0b11 )
n++;

t |= (n&1)<<i++;
n >>>= 1;
}

return t;
}``````

Comment hidden because of low score. Click to expand.
0

Hmmm ... Somehow a stray ";" found it's way in there. It should read:

t |= (n&1)<<i++;

Comment hidden because of low score. Click to expand.
0

Just in case it's not clear from the Java code I provided, here's a walkthrough.

Given the parameters of the question:
1) "Sparse number is an integer if there are no adjacent 1 in it's binary representation."
2) "Now you are given an integer find the NEXT BIGGER sparse number."

Also of note:
1) nowhere does it specify that the input integer is necessarily sparse
2) it does not specify that an input is necessarily positive (although for those who remember that input will be represented as a 2's-compliment, it should be obvious, and why).

So, that said:

// By definition, and to satisfy #2 above, the
// next larger sparse <must> be at least one
// greater than the input value.
n++;

// 't' will be our result value
long t = 0;

// 'i' is a local value we're using for a counter.
int i = 0;

// We're using this as our terminating condition,
// it guarantees O(n) complexity because we're
// shifting 'n' by one bit in each iteration of this loop.
while( n > 0 )
{
// Evaluate the least significant bit of 'n', as well as
// the next more significant bit, for adjacent 1's
// as per stipulation # 1.
if( (n&0b11) == 0b11 )
// the value, this addition operation will
// sequentially overflow all the adjacent non-zero
// bits, forcing this portion of the integer to
// become 'sparse'.
n++;

// 1) We're taking the [currently] least significant bit from 'n'.
// 2) Then we're shifting it left by 'i' bits, where 'i' is the
// number of iterations through this loop.
// 3) Post-incrementing 'i' to match the number of bits we will
// have shifted out of 'n' by the end of this loop (below).
// 4) We're placing the 'i'-th bit from 'n' (above) into the
// 'i'-th bit of the result value.
t |= (n&1)<<i++;

// Do an unsigned (so as to prevent the most
// significant bit from inappropriately propagating
// in due to a signed shift operation) shift to remove
// the bit we've just evaluated.
n >>>= 1;
}

// Return the result
return t;

Comment hidden because of low score. Click to expand.
0
of 2 vote

Guys no good answer for this question????please post if anyone have idea!!

Comment hidden because of low score. Click to expand.
0

Check my answer below. Two approaches (both are pretty much one and same)

Comment hidden because of low score. Click to expand.
1
of 1 vote

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````int findNextSparse(int n)
{
bool bOne = false;
int current = n;
bool bFound = false;

while(!bFound)
{
current = ++n;

while(current != 0)
{
if(current & 0x1 == 1)
{
if(bOne)
{
bFound = false;
break;
}

bOne = true;
}else
{
bOne = false;
}

current = current >> 1;
}

if(current == 0)
bFound = true;
}

return n;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
using namespace std;

bool sparse(int n){
return ( (n & (n>>1)) == 0);
}

int nextSparse(int n){
if(sparse(n))
n+=1;

int limit=sizeof(int)*8-1;
for(int i=0; i<limit; i++ ){
//cout<<n<<endl;
if(sparse(n))
break;

}
}

return n;
}
int main() {
cout<<nextSparse(18);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int find_max_double_one_index(int n)
{
auto nt = n;
auto prev_one = nt & 1;
auto max_i = -1;
nt >>= 1;
auto i = 1;
while (nt)
{
if (nt & 1)
{
if (prev_one)
{
max_i = i;
}
prev_one = true;
}
else
{
prev_one = false;
}
nt >>= 1;
++i;
}
return max_i;
}

int next_sparse(int n)
{
auto i = find_max_double_one_index(n);
if (-1 == i)
{
++n;
i = find_max_double_one_index(n);
}
while (-1 != i)
{
n &= (~0 << (i + 1));
n |= (1 << (i + 1));
i = find_max_double_one_index(n);
}
return n;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It seems you can just add 1 and walk from right to left and every time you encounter two 1's together shift right, add 1, and shift back left.

``````public static int getNextSparse(int in) {
int num = in + 1;
int shift = 0;
num = ((num >> shift) + 1) << shift;
}
shift++;
}
return num;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my attempt. I didn't test it too thoroughly, but I did test it a little bit and it seems sane. Basically, starting the lsb and moving to msb - 1, I'm making sure that the current offset is sparse. If it isn't, I increment the number just at that offset. It's not "brute force", since since it's bounded only by the size of an integer in terms of comparisons.

``````// Given an integer, find the next biggest integer which is "sparse".
public static int FindNextSparse(int number)
{

++number;

for (int i = 0; i < 31; ++i)
{
// Starting from idx, increment number at index until this portion of the number is no longer sparse.
if (((number >> i) & 3) == 3)
{
number = (number & mask) | ((((number & ~mask) >> i) + 1) << i);
}

}

return number;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Tested on a couple simple cases. It requires no more than 31 comparisons, since it increments the number at the current offset once if it detects a sparse condition.

``````// Given an integer, find the next biggest integer which is "sparse".
public static int FindNextSparse(int number)
{

++number;

for (int i = 0; i < 31; ++i)
{
// Starting from idx, increment number at index until this portion of the number is no longer sparse.
if (((number >> i) & 3) == 3)
{
number = (number & mask) | ((((number & ~mask) >> i) + 1) << i);
}

}

return number;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <windows.h>
#include <stdio.h>
#include <stdlib.h>

BOOL
issparce(ULONG num)
{
ULONG num2 = num >> 1;
if (num2 & num)
{
return FALSE;
}
return TRUE;
}

int __cdecl wmain(
int argc,
__in_ecount(argc) PWSTR *argv
)
{
ULONG num = _wtoi(argv);
++num;

while (!issparce(num))
{
num++;
}
wprintf(L"next sparce num %d\n", num);

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

test

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Firstly: Brute force is NOT feasible for this problem. Note that, in the worst case, we need to go from 101010...1010 to 100000...0000. The difference between these two numbers grows exponentially.

Note, it is very easy to find the previous sparse number, if we are given a non-sparse number. I will briefly outline this method, and proceed as if we are always given a sparse number.

To find the PREVIOUS sparse number, we go along a number from left to right. If we ever find consecutive ones, we turn the second into a 0 and - if it is not one already - we turn the digit after this into a one. We have a boolean to record if we have made any changes already (i.e. decreased our number). If we have, and we come across consecutive 0s, we will change the second one into a 1. I will leave it to you to confirm that a) this will always leave a sparse number b) it will be precisely the first sparse number below our given number. It's a good exercise to try coding this.

Now, how do we find the next sparse number when we are given a sparse number? This method is based on the fact that the nth sparse number is the ZECKENDORF REPRESENTATION* of n. So, from right (least significant digit) to left, we keep track on the nth Fibonacci number (initialising with f_1 = 1, f_2 = 2), and if there is a one in that place, we add this fib number to our sum. The sum of these Fibonacci numbers will be the number which this is representation of. Now, all we need to do is find the Zeckendorf representation of the next number. But this is trivially possible with a greedy algorithm. So we are done, much quicker than brute force.

Is there a better way? Perhaps. Please let me know if you find one; I can't see a trivial way to find the next number in the same way we can find the previous one, but there probably is a way.

* You may want to look this term up, but briefly, if we have the number, say 101001, then this represents 1 + 5 + 13 = 19, because we are summing the first, fourth and sixth fibonacci numbers. We can find the representation for n by adding the highest fibonacci number less than or equal to n, so long as the fib number directly above is not already in our representation.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Firstly: Brute force is NOT feasible for this problem. Note that, in the worst case, we need to go from 1010...1010 to 100000...0000. The difference between these two numbers grows exponentially.

Note, it is very easy to find the previous sparse number, if we are given a non-sparse number. I will briefly outline this method, and proceed as if we are always given a sparse number.

To find the PREVIOUS sparse number, we go along a number from left to right. If we ever find consecutive ones, we turn the second into a 0 and - if it is not one already - we turn the digit after this into a one. We have a boolean to record if we have made any changes already (i.e. decreased our number). If we have, and we come across consecutive 0s, we will change the second one into a 1. I will leave it to you to confirm that a) this will always leave a sparse number b) it will be precisely the first sparse number below our given number.

Now, how do we find the next sparse number when we are given a sparse number? This method is based on the fact that the nth sparse number is the ZECKENDORF REPRESENTATION* of n. So, from right (least significant digit) to left, we keep track on the nth fibonacci number (initialising with f_1 = 1, f_2 = 2), and if there is a one in that place, we add this fib number to our sum. The sum of these fibonacci numbers will be the number which this is representation of. Now, all we need to do is find the Zeckendorf representation of the next number. But this is trivially possible with a greedy algorithm. So we are done, much quicker than brute force.

Is there a better way? Perhaps. Please let me know if you find one; I can't see a trivial way to find the next number in the same way we can find the previous one, but there probably is a way.

* You may want to look this term up, but briefly, if we have the number, say 101001, then this represents 1 + 5 + 13 = 19, because we are summing the first, fourth and sixth fibonacci numbers. We can find the representation for n by adding the highest fibonacci number less than or equal to n, so long as the fib number directly above is not already in our representation.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

My last comment did not show up, but I have optimised the method anyway:

Again, note that brute force will NOT work. Going from 1010...1010 to 1000...0000 will be our worst case, and this difference grows exponentially.

First, if the given number is not sparse, we find the PREVIOUS sparse number. This is very easy, and we can then simply solve the problem as if only given sparse numbers:

For a non-sparse number, work from the left until we find the first pair of consecutive 1s. Then, change the second number into a 0, and fill in the rest of the number with the pattern "1010..10". i.e. 1001101011 -> 1001001011 -> 1001010101. Proof that this is the previous sparse number is not given, but it is similar to that given below if you wish to attempt it.

Now, we just need to find the next sparse number if given a sparse number:

Method 1) This is the slick way to do it. Working from the right hand side, wait until we find the first pair of consecutive zeros (if no pair exists, i.e. the number is of the form 1010101(0), then "pad" with 00s at the start, so we have 001010101(0)). Change the second 0 into a 1, and change everything below to a 0.

Proof this is sparse: trivial; our original number was sparse, and we have certainly not added any consecuutive 1s.
Proof it is the next sparse number: our sparse number must have ended ...0010101(0) [WLOG: there can be any number of "01" pairs at the end, or none at all), and everything up to and including the first zero is unchanged. Our "next" number is ...0100000(0). Both are sparse - is there a sparse number between them? If there is, it must be of the form ...00xxxxx (as our found number is the minimum number of the form ...01xxxxx(0)). But our original number is the maximum sparse number of this form (a 1 is continuously put as early as possible to remain sparse)! QED.

Method 2) Note that the nth sparse number is the Zeckendorf representation of n. So we find out which number our sparse number reprsents, say "m", then find the representation of m+1. It is easy to do both of these things, if you understand Zeckendorf representations (which you may wish to look up), and no proof of correctness is needed because it follows immediately from Zeckedorf's theorem. Here is an example:

10100101 represents 1 + 3 + 13 + 34 = (f_1 + f_3 + f_6 + f_8) = 51. So we need to find the representation of 52. The largest fib number less than or equal to 52 is 34, so our number is of the form 10xxxxxx. We now need to find the next fib number below 52-34 EXCLUDING 21. In this case, 21 is not in the considered set anyway, but this is just a warning that you need to be careful here. We see that 13 fits, so our number is now of the form 1010xxxx. Continuing in this way, We find 52 = 34 + 13 + 5, which corresponds to the representation "10101000", which is our answer. Note that this is a simple greedy algorithm and has a very fast running time.

Comment hidden because of low score. Click to expand.
0

Finally it showed up. Sorry for the spam :D

I did a quick Java implementation of method 1, with a few comments (but the method is explained above mainly). It could be sped up with built in commands (e.g. taking logs base 2, using in-built binary converters), but I avoided this and used only arrays and basic operations so anybody can read. Any errors please let me know.

``````public class SparseBinary2{
public static void main(String[] args){
for(int i = 0; i <= 64; i++){
System.out.println(i + "\t" + nextSparse(i));
}
}
static int nextSparse(int n){
// special case
if(n==0) return 1;
//find length of binary form
int pow = 1, l = 1;
while(pow*2 <= n){
pow*=2; l++;
}
//put binary form into an array
int[] arr = new int[l];
int index = 0, m = n;
//System.out.println("n = " + n + " l = " + l);
for(int i = 0; i < l; i++){
//System.out.println(i + " " + (l-i));
if(m%2 == 1){
arr[l-1-i] = 1;
}
m/=2;
}
//turn into sparse, if not already;
int count = 0;
for(int i = 0; i < l-1; i++){
if(arr[i]==1){
if(count==0){
count++;
}
else{
for(int pos = 0; pos+i<l; pos++){
arr[i+pos] = pos%2;
}
break;
}
}
else{
count = 0;
}
}
//find next sparse
boolean found = false;
for(int i = l-1; i > 0; i--){
if(arr[i]==0 && arr[i-1]==0){
arr[i] = 1;
for(int j = 1; j+i < l; j++){
arr[i+j] = 0;
}
found = true; break;
}
}
//convert binary to a number;
pow = 1;
int ret = 0;
for(int i = l-1; i >= 0; i--){
if(arr[i] == 1){
ret+=pow;
}
pow*=2;
}
if(found) return ret;
else return pow;
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Scan right to left (i.e. lsb to msb) and for a 1 followed by 0 swap it and check if number left to swapped digits (including swapped digits) is sparse or not, if it is then we need to reset bits following swapped digits bits to 0 (by an &) and that's our answer.

e.g. given number 100101, here {} denotes 1 and 0 being swapped.
1001{10}
10{10}10 => 10{10} is sparse number, reset trailing 1's to 0 which are right side of {}

e,g, given number 100100
10010{1} ( 10010{1} is a sparse number)
10010{1} (reset trailing 1's right of {1})

e,g, given number 100111
10{10}11 (10{10} is sparse, remove trailing 11 following {10})

e.g. given number 11011 (which is same as 011011)
011{10}1
{10}1101 (0{10} is sparse, reset bits following {})

e.g. given number

Comment hidden because of low score. Click to expand.
0

On the second thought, the earlier approach is nothing but adding 1,2,4,8,... numbers to the original number and resetting the trailing digits

General idea in pseudo code, without handling off by one errors etc
here MSB is most significant bit

``````int FindSparseNumber(int Number)
{
int Multiplier = 1; // multiplier will be 1, 2, 4, 8, ...
while(MSB of Number is not reached)
{
int nextNumber = Number | Multiplier;
nextNumber &= Multiplier ; (remove trailing 1's)
if(IsSparse(nextNumber))
{
return nextNumer;
}
Multiplier = Multiplier<;1; // multiply by 2
}
return Mutliplier; // handle '111', upon termination, Multiplier will be 1000
}``````

Comment hidden because of low score. Click to expand.
0

Sorry
int nextNumber = Number + Multiplier;

int nextNumber = Number | Multiplier;

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Earlier I replied the answer, swapping 0 with 1 and (somehow I don't see it being posted yet. maybe it takes time)
On the second thought, the earlier approach is nothing but adding 1,2,4,8,... numbers to the original number and resetting the trailing digits

General idea in pseudo code, without handling off by one errors etc
here MSB is most significant bit

``````int FindSparseNumber(int Number)
{
int Multiplier = 1; // multiplier will be 1, 2, 4, 8, ...
while(MSB of Number is not reached)
{
int nextNumber = Number | Multiplier;
nextNumber &= Multiplier ; (remove trailing 1's)
if(IsSparse(nextNumber))
{
return nextNumer;
}
Multiplier = Multiplier<1; // multiply by 2
}
return Mutliplier; // handle '111', upon termination, Multiplier will be 1000
}``````

Comment hidden because of low score. Click to expand.
0

Sorry
int nextNumber = Number + Multiplier;

int nextNumber = Number | Multiplier;

Comment hidden because of low score. Click to expand.
-1
of 1 vote

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static boolean check_sparse(int num)
{
int prev =0;
while(num>0)
{
int bit = num&1;
if(bit==1&& prev ==1)
{
return false;
}
prev = bit;
num = num>>1;
}
return true;
}

static int return_next_sparse(int num)
{
int i = num +1;
while(true)
{
if(check_sparse(i))
break;
i++;
}
return i;
}

public static void main (String[] args) throws java.lang.Exception
{
System.out.println(return_next_sparse(4));
System.out.println(return_next_sparse(5));
System.out.println(return_next_sparse(1));
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static boolean check_sparse(int num)
{
int prev =0;
while(num>0)
{
int bit = num&1;
if(bit==1&& prev ==1)
{
return false;
}
prev = bit;
num = num>>1;
}
return true;
}

static int return_next_sparse(int num)
{
int i = num +1;
while(true)
{
if(check_sparse(i))
break;
i++;
}
return i;
}

public static void main (String[] args) throws java.lang.Exception
{
System.out.println(return_next_sparse(4));
System.out.println(return_next_sparse(5));
System.out.println(return_next_sparse(1));
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static boolean check_sparse(int num)
{
int prev =0;
while(num>0)
{
int bit = num&1;
if(bit==1&& prev ==1)
{
return false;
}
prev = bit;
num = num>>1;
}
return true;
}

static int return_next_sparse(int num)
{
int i = num +1;
while(true)
{
if(check_sparse(i))
break;
i++;
}
return i;
}

public static void main (String[] args) throws java.lang.Exception
{
System.out.println(return_next_sparse(4));
System.out.println(return_next_sparse(5));
System.out.println(return_next_sparse(1));
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

It looks like it follows a pattern.

1. Find N, the nearest power of 2 and check for numbers
N + {(2^0), (2^1), (2^2, 2^2 + 1), (2^3, 2^3 + 1, 2^3 + 2), (2^4, 2^4 + 1, 2^4 + 2, 2^4 + 3) and so on}
2. Exclude N + N/2
3. Stop the loop once calculated value is greater than given number.

``````Find N = Nearest power of 2 less than or equal to the given number
Find K Where 2 Power K = N
Start = 1
If Given Number = 1, Return 2
While Start <= N
If (Start != N/2)
For I = 0 To K - 1
If N + I > Given Number
Return N + I
End If
Loop
End If
Start = Start * 2
Loop``````

For Example, If Given number is 10
Find N = 2 ^ 3 = 8
Now try
8 + 2^0 = 9 < Given Number so continue
8 + 2^1 = 10 = Given Number so continue
Ignore 2^2 as It is equal to N/2.
8 + 2^3 = 16 > Given Number so Return 16

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Easy one. Basically check for patterns of 3 bytes where you can swap a byte e.e. 000 -> 010

``````private static int nextSparse(int originalVal) {
int x = originalVal;
int shifts = 0;

if((x & 3) == 0) {
return x + 1;
}
if((x & 7) == 1) {
return x -1 + 2;
}

while(x > 1){
if((x & 7) == 1){
return originalVal+ (1<<shifts+1) - (1<<shifts);
}
shifts++;
x = x >> 1;
}
return (1 << shifts+1);
}``````

Comment hidden because of low score. Click to expand.
0

``````long NextSparseNumber(long number)
{
long i = number;
long shift;
for (shift = 0; i > 0; shift++, i=i>>1)
{
if (!(i & 3))
return i + 1 << shift;
else if ((i & 7) == 1)
return 1 << (shift + 1) > number ? 1 << (shift + 1) : number - (1 << shift) + (1 << (shift + 1));
}
return number == 0 ? 1 : 1 << (shift + 1);
}``````

Test cases:

``````assert(NextSparseNumber(0) == 1);
assert(NextSparseNumber(1) == 2);
assert(NextSparseNumber(2) == 4);
assert(NextSparseNumber(3) == 4);
assert(NextSparseNumber(4) == 5);
assert(NextSparseNumber(5) == 8);
assert(NextSparseNumber(6) == 8);
assert(NextSparseNumber(7) == 8);
assert(NextSparseNumber(8) == 9);
assert(NextSparseNumber(9) == 10);``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is not a optimized solution but this should work.

public class Test {

public static void main(String arg[])
{
boolean sparseFound = false;
int currentNumber = 82;
while(!sparseFound)
{
currentNumber++;
sparseFound = checkForSparse(currentNumber);
if(sparseFound == true)
System.out.println(currentNumber);
}
}

private static boolean checkForSparse(int currentNumber) {
boolean lastBitSet = false;

int nextNumberBitSet;
int bitIndex = 1;
for(int i = 1; i <= 32;i++){
nextNumberBitSet = currentNumber & bitIndex;
if(nextNumberBitSet > 0 ){
if(lastBitSet)
return false;
lastBitSet = true;
}
else
{
lastBitSet = false;
}
bitIndex = bitIndex<<1;
}
return true;
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class Test
{
public static void main(String arg[])
{
boolean sparseFound = false;
int currentNumber = 5;
while(!sparseFound)
{
currentNumber++;
sparseFound = checkForSparse(currentNumber);
if(sparseFound == true)
System.out.println(currentNumber);
}
}

private static boolean checkForSparse(int currentNumber) {
boolean lastBitSet = false;

int nextNumberBitSet;
int bitIndex = 1;
for(int i = 1; i <= 32;i++){
nextNumberBitSet = currentNumber & bitIndex;
if(nextNumberBitSet > 0 ){
if(lastBitSet)
return false;
lastBitSet = true;
}
else
{
lastBitSet = false;
}
bitIndex = bitIndex<<1;
}
return true;
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

private static int getNextSparseNumber(int input) {
while(true){
input++;
s= "";
toBin(input);
if(isSparseNumber()){
//System.out.println("Next Sparse Number : "+input);

break;
}

}
return input;
}

private static boolean isSparseNumber(){

for(int i = 0; i < s.length()-1; i++){
if(s.charAt(i) == '1' && s.charAt(i+1) == '1'){
return false;
}
}
return true;

}

private static void toBin(int n){
if(n!=0){
toBin(n/2);
s += n %2;
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

import java.io.*;
import java.util.*;
import java.util.Scanner;

public class SparseNumber {

static String s = "";

public static void main(String args[]){
Scanner in = new Scanner(System.in);
while(true){
int input = in.nextInt();
System.out.println(getNextSparseNumber(input));
}

}

private static int getNextSparseNumber(int input) {
while(true){
input++;
s= "";
toBin(input);
if(isSparseNumber()){
//System.out.println("Next Sparse Number : "+input);
break;
}

}
return input;
}

private static boolean isSparseNumber(){

for(int i = 0; i < s.length()-1; i++){
if(s.charAt(i) == '1' && s.charAt(i+1) == '1'){
return false;
}
}
return true;

}

private static void toBin(int n){
if(n!=0){
toBin(n/2);
s += n %2;
}
}

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static void main(String[] args) {
int start = 9;
int cur = start;
int check = 0;

while (check != -1) check = isSparseInteger(cur++,0);

System.out.println(start + " NEXT BIGGER is " + cur);

}
private static int isSparseInteger(int i,int adj) {
if (i<0 || adj < 0) return -1;
if (i>0) {
int a = i/2;
int bin = a%2 == 0 ? 0:1;
if (adj+bin == 2)  return -1;
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public 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);
}
}``````

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public 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);
}
}``````

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This is linear in the number of digits of the number n (i.e., O(log n)).

The idea is to increment the given number by 1, and replace "11" with "100" in the binary representation. (This is done by adding a suitable power of 2.)

The interesting point here is to check, at the end, if we can erase some 1s towards the least significant bit.

``````public static int nextSparse(int n) {
int tmp = n + 1;
int i = 0;
// "replace" 11 with 100
while ((tmp >> i) != 0) {
if (((tmp >> i) & 3) == 3) {
tmp += (1 << i);
}
++i;
}
// since we added at the beginning,
// we need to check if we can remove 1s
// towards the lsb
i = 0;
while (((tmp >> i) << i) > n) {
tmp = (tmp >> i) << i;
++i;
}
return tmp;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

/*
* Sparse number is an integer if there are no adjacent 1 in its binary
* representation
* Like 5 - > 101 (no adjacent 1)
* 9 - > 1001 ( no adjacent 1)
* while 6 -> 110 is not sparse number.
* Now you are given an integer find the Next bigger sparse number.
* Please mind 'it is next bigger'
*/
public class SparseNumber {
public static boolean isSparseNumber(int number) {
boolean result = true;
int b = 0;
while(number != 0) {
if((number & 1) == 1) {
b++;
} else {
b--;
}
if(b > 1) {
result = false;
break;
}
number = number >> 1;
}
return result;
}

public static int nextBiggerSparshNumber(int number){
int result = Integer.MIN_VALUE;
while(true) {
number = number + 1;
if(isSparseNumber(number)) {
result = number;
break;
}
}
return result;
}
public static void main(String[] args) {
/*System.out.println(isSparseNumber(9));
System.out.println(isSparseNumber(8));
System.out.println(isSparseNumber(7));
System.out.println(isSparseNumber(6));
System.out.println(isSparseNumber(5));*/

System.out.println(nextBiggerSparshNumber(6));
}

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

/*
* Sparse number is an integer if there are no adjacent 1 in its binary
* representation
* Like 5 - > 101 (no adjacent 1)
* 9 - > 1001 ( no adjacent 1)
* while 6 -> 110 is not sparse number.
* Now you are given an integer find the Next bigger sparse number.
* Please mind 'it is next bigger'
*/
public class SparseNumber {
public static boolean isSparseNumber(int number) {
boolean result = true;
int b = 0;
while(number != 0) {
if((number & 1) == 1) {
b++;
} else {
b--;
}
if(b > 1) {
result = false;
break;
}
number = number >> 1;
}
return result;
}

public static int nextBiggerSparshNumber(int number){
int result = Integer.MIN_VALUE;
while(true) {
number = number + 1;
if(isSparseNumber(number)) {
result = number;
break;
}
}
return result;
}
public static void main(String[] args) {
/*System.out.println(isSparseNumber(9));
System.out.println(isSparseNumber(8));
System.out.println(isSparseNumber(7));
System.out.println(isSparseNumber(6));
System.out.println(isSparseNumber(5));*/

System.out.println(nextBiggerSparshNumber(6));
}

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public class NexBiggerSParseNum {
static String temp;

public static void main(String[] args) {
int num = 72;
int len;

for (int i= num+1; i < Integer.MAX_VALUE ; i++){
if(isSparseNum(i)){
System.out.println("Next Parse Num is "+i);
break;
}
}

}

public static boolean isSparseNum(int num){
temp = Integer.toBinaryString(num);
return temp.indexOf("11")>0?false:true;
}

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include <iostream>
using namespace std;

bool sparse(int n){
return ( (n & (n>>1)) == 0);
}

int nextSparse(int n){
if(sparse(n))
n+=1;

int limit=sizeof(int)*8-1;
for(int i=0; i<limit; i++ ){
//cout<<n<<endl;
if(sparse(n))
break;

}
}

return n;
}
int main() {
cout<<nextSparse(18);
return 0;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````public static void Run()
{
int val, orig;
val = orig = 22;
int checker = 1;

// How many significant bits do we have
int log = (int)Math.Log(orig, 2) + 1;

int zc = 0;
int oc = 0;

for(int i = 0; i <= 15; i++)
{
// Check next bit
if((val & checker) == checker)
{
// Drop zeros count and increase ones	count
zc = 0;
oc++;
}
else
{
// Drop ones count and increase zeros	count
zc++;
oc = 0;
}

// Found tow zeroes?
if(zc == 2)
{
// Transform previous zero to one
val |= checker >> 1;

// Clear the rest bits
val &= ~(checker >> 1) + 1;

// Clear counters
zc = 0;
oc = 0;
}

// Found two ones?
if(oc == 2)
{
// Transform the current bit to zero
val ^= checker;

// Transform the next bit to one. If it is already one nothing will happen
if(checker != int.MaxValue)
val |= checker << 1;

// Clear counters
zc = 0;
oc = 0;
}

// We found next number and already checked all significant bits? End search
if(val > orig && (int)Math.Pow(log, 2) <= checker)
{
break;
}

// Shift to next bit
checker = checker << 1;
}

Console.Write(val);
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````int nextSparserNumber(int x)
{
int ans = 0, mask = 1; x += 1;

while (x != 0)
{
while ((x & 1) == 0)
{
x >>= 1; mask <<= 1;
}

int cnt = 0;

while ((x & 1) == 1)
{
++cnt; x >>= 1; mask <<= 1;
}

if (cnt > 1)
{
x += 1;
}
else
{
}
}

return ans;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Time 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;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````/*
Sparse number is an integer if there are no adjacent 1 in it's binary representation.
Like: 5 -> 101 (no adjacent 1)
9 -> 1001 (no adjacent 1)
while 6-> 110 is not sparse number.
Now you are given an integer find the NEXT BIGGER sparse number.Please mind 'it is next bigger'.
*/

#include<iostream>
using namespace std;

int countBits(int num)
{
if(num)
{
return 1+countBits(num>>1);
}
return 0;
}

int getPosition(int num, int count)
{
int temp = num;
for(int i=0;i<count-1;i++)
{
if(!((temp>>i) & 1) && !((temp>>(i+1))&1))
return i;
}
return -1;
}

int function(int num)
{
int n = countBits(num);
int pos = getPosition(num, n);

if(pos == -1)
return num<<1;
else if(!pos)
return num | 1;
else
{
int num1 = (num >> pos)<<pos;
int num2 = (num & ((2<<pos)-1))<<1;
return  (num1 | num2);
}
}

int main()
{
int num;
cout<<"  Enter number :- ";
cin>>num;
int sparse = function(num);
cout<<"  Sparse Number is :- "<<sparse<<endl;
system("PAUSE");
return 0;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<stdio.h>
#include<stdlib.h>

int main()
{
int number,x;
int sparse(int); // prototype of function
printf("Enter the number:");
scanf("%d",&number);

while(1)
{
x=sparse(++number);
if(x==1) // means nearest sparse number found
{
printf("%d",number);
break;
}
}
}

int sparse(int number)
{
int binary;
int quotient;
int i=1,j;

// 1st convert the number into its binary equivalent
binary=number%2;
quotient=number/2;
while(quotient!=0)
{
binary[i++]=quotient%2;
quotient=quotient/2;
}

/* Need not to reverse the binary[] to get the correct binary number */
// check whether there are two consectives 1 in the representation

for(j=0;j<i-1;j++)
{
if(binary[j]==1 && binary[j+1]==1)
return 0;
}
return 1;
}

Comment hidden because of low score. Click to expand.
-2
of 2 vote

For non sparse numbers, there's not really way to generalize getting a bigger sparse number, so here you just have to increment the number, check if sparse, increment, check (so on and so forth in the brute force approach. Now, let's look at sparse bitstrings:

Assuming they have greater than or equal to 4 bit positions, we can see something:

If it ends in:

1000, we can keep it sparse by adding 1

x1000 -> x1001

If it ends in:

1010, we keep it sparse by adding a 0,

x1010 -> x10100

If it ends in 1001:

x1001 -> 1010

For all other combinations of sparse bitstring, we will do the brute force approach, but this is a quick optimization

Comment hidden because of low score. Click to expand.
0

Your answer for 1010 is not correct. While 10100 is sparse int, it is not next sparse int. 10000 would be the next sparse int.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.