<p>Given a positive integer <code>n</code>, return the number of the integers in the range <code>[0, n]</code> whose binary representations <strong>do not</strong> contain consecutive ones.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 5
<strong>Output:</strong> 5
<strong>Explanation:</strong>
Here are the non-negative integers &lt;= 5 with their corresponding binary representations:
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 2
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {

    int memoize (int i, string& start, string& end, bool isUpperBound, bool isLastOne, int dp[][2][2]) {
        if (i == end.size()) return 1;
        int ub = isUpperBound ? 1:0;
        int lo = isLastOne ? 1:0;
        if (dp[i][lo][ub] != -1) return dp[i][lo][ub];
        char from = '0';
        char to = (isUpperBound) ? end[i] : '1';
        int ans = 0;
        for (char ch = from; ch <= to; ch++) {
            if (isLastOne && ch == '1') continue;
            ans += memoize(i+1, start, end, isUpperBound && (ch==to), (ch=='1'), dp);
        }
        dp[i][lo][ub] = ans;
        return ans;
    }

    string to_binary(int n) {
        string ans = "";
        while (n>0) {
            char ch = (n%2==1) ? '1' : '0';
            ans.push_back(ch);
            n/=2;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }

public:
    int findIntegers(int n) {
        string end = to_binary(n);
        int x = end.size();
        string start(x, '0');
        int dp[x+1][2][2];
        for (int i=0; i<=x; i++)
            dp[i][0][0] = dp[i][1][0] = dp[i][1][1] = dp[i][0][1] = -1;
        int ans = memoize(0, start, end, true, false, dp);
        return ans;
    }
};
8200