<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 {
public:
    int dp[34][2][2][2];
    int rec(int i,int lst,int sz,int tlo,int thi,string &a,string &b)
    {
        if(i==sz)
        {
            return 1;
        }
        if(dp[i][tlo][thi][lst]!=-1)
        return dp[i][tlo][thi][lst];
        int lo=0;
        int hi=1;
        if(tlo==1)
        lo=a[i]-'0';
        if(thi==1)
        hi=b[i]-'0';
        if(lst==1)
        {
            hi=0;
        }
        int ret=0;
        for(int j=lo;j<=hi;j++)
        {
            int nlo=0,nhi=0;
            if(j==lo)
            nlo=tlo;
            if(j==b[i]-'0')
            nhi=thi;
            ret=ret+rec(i+1,j,sz,nlo,nhi,a,b);
        }
        // cout<<lo<<" "<<hi<<endl;
        // cout<<i<<" "<<tlo<<" "<<thi<<" "<<lst<<" "<<ret<<endl;
        return dp[i][tlo][thi][lst]=ret;
    }
    int findIntegers(int n) {
        string b="";
        while(n>0)
        {
            if(n%2)
            b+='1';
            else
            b+='0';
            n/=2;
        }
        reverse(b.begin(),b.end());
        string a="";
        while(a.size()<b.size())
        {
            a+='0';
        }
        int ret=0;
        memset(dp,-1,sizeof(dp));
        int sz=a.size();
        ret=rec(0,0,sz,1,1,a,b);
        return ret;
    }
};
8200