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