# Next Sparse Number

# Question

http://www.lintcode.com/en/problem/next-sparse-number/

A number is Sparse if there are no two adjacent 1s in its binary representation. Given a number n, find the smallest Sparse number which greater than or equal to n.

eg. 5 (binary representation: 101) is sparse, but 6 (binary representation: 110) is not sparse.

# Example

Given n = 6, return 8

Next Sparse Number is 8

Given n = 4, return 4

Next Sparse Number is 4

Given n = 38, return 40

Next Sparse Number is 40

Given n = 44, return 64

Next Sparse Number is 64

Given n = 341381939, return 343932928

Next Sparse Number is 343932928

# Answer

```
class Solution {
public:
/*
* @param : a number
* @return: return the next sparse number behind x
*/
int nextSparseNum(int x) {
// write your code here
if (x == 0 || x == 1) return x;
string binary;
int n = x;
while (n) {
if (n&1)
binary.append("1");
else
binary.append("0");
n >>= 1;
}
for (int i = 1; i < binary.length(); i++) {
if (binary[i] == '1' && binary[i-1] == '1') {
// plus 1 from i-1
int c = 1;
int j = i-1;
while (c == 1 && j < binary.length()) {
int t = binary[j] - '0' + c;
if (t < 2) {
c = 0;
binary[j] = t + '0';
} else {
c = 1;
binary[j] = '0';
}
j++;
}
if (c == 1)
binary.append("1");
}
}
int result = 0;
for (int i = 0; i < binary.length() - 1; i++) {
if (binary[i] == '1') {
string nb = binary;
nb[i] = '0';
int nx = bintoint(nb);
if (nx >= x) {
binary[i] = '0';
if (result == 0)
result = nx;
else if (result > nx)
result = nx;
}
}
}
if (result == 0)
result = bintoint(binary);
return result;
}
inline int bintoint(string& binary) {
int result = 0;
for (int i = binary.length(); i > 0; i--)
result += (binary[i-1] - '0') << (i-1);
return result;
}
};
```