## Amazon Interview Question

SDE-2s**Country:**United States

**Interview Type:**Phone Interview

There are 2 possible number types you are going to deal with:

1. already sparse number

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

"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.

"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.

@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.

I think your idea works!

Can improve your answer with a clearer explanation and shorter code?

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

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

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;

}

}

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

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 )

// If there are adjacent ones, then add one to

// 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;

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

```
#include <iostream>
using namespace std;
bool sparse(int n){
return ( (n & (n>>1)) == 0);
}
int nextSparse(int n){
if(sparse(n))
n+=1;
int mask=3;
int adder=1;
int limit=sizeof(int)*8-1;
for(int i=0; i<limit; i++ ){
//cout<<n<<endl;
//cout<<(n&mask)<<" "<<mask<<endl;
if(sparse(n))
break;
if((n&mask)==mask){
n=n+adder;
}
mask=mask<<1;
adder=adder<<1;
}
return n;
}
int main() {
// your code goes here
cout<<nextSparse(18);
return 0;
}
```

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

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 mask = 0b11;
int shift = 0;
while(0 <= Integer.compareUnsigned(num, mask)) {
if((num & mask) == mask) {
num = ((num >> shift) + 1) << shift;
}
mask <<= 1;
shift++;
}
return num;
}
```

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)
{
// mask of the already visited part of number.
int mask = 0;
++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);
}
mask |= (1 << i);
}
return number;
}
```

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)
{
// mask of the already visited part of number.
int mask = 0;
++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);
}
mask |= (1 << i);
}
return number;
}
```

```
#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[1]);
++num;
while (!issparce(num))
{
num++;
}
wprintf(L"next sparce num %d\n", num);
return 0;
}
```

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.

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.

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.

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

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 {}

10{10}00 => final answer

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})

10{10}00 (answer)

e.g. given number 11011 (which is same as 011011)

011{10}1

{10}1101 (0{10} is sparse, reset bits following {})

{10}0000 answer

e.g. given number

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

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

/* 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));

}

}

/* 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));

}

}

/* 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));

}

}

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

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

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

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;

}

}

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;

}

}

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;

}

}

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;

}

}

}

```
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;
else adj = bin;
return isSparseInteger(a, adj);
}
return 0;
}
```

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

}

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

}

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) {
// add 1
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;
}
```

/*

* 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));

}

}

/*

* 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));

}

}

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;

}

}

#include <iostream>

using namespace std;

bool sparse(int n){

return ( (n & (n>>1)) == 0);

}

int nextSparse(int n){

if(sparse(n))

n+=1;

int mask=3;

int adder=1;

int limit=sizeof(int)*8-1;

for(int i=0; i<limit; i++ ){

//cout<<n<<endl;

//cout<<(n&mask)<<" "<<mask<<endl;

if(sparse(n))

break;

if((n&mask)==mask){

n=n+adder;

}

mask=mask<<1;

adder=adder<<1;

}

return n;

}

int main() {

// your code goes here

cout<<nextSparse(18);

return 0;

}

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

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

```
/*
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;
}
```

#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[100];

int quotient;

int i=1,j;

// 1st convert the number into its binary equivalent

binary[0]=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;

}

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

- Vir Pratap Uttam May 11, 2015