<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 solve(int n, int take ,int tight, int one, vector<vector<vector<int>>>& dp)
    {
        if(take<0)
        return 1;
        int count=0;
        if(dp[take][tight][one]!=-1)
        return dp[take][tight][one];
        if(tight)
        {
            int ind=0;
            if(n & (1<<take))
            ind=1;
            for(int i=0;i<=ind;i++)
            {
                if(i==1 && one)
                continue;
                if(i==ind)
                {
                    if(i==1)
                    count+=solve(n,take-1,1,1,dp);
                    else
                    count+=solve(n,take-1,1,0,dp);
                }
                else
                {
                    if(i==1)
                    count+=solve(n,take-1,0,1,dp);
                    else
                    count+=solve(n,take-1,0,0,dp);
                }
            }
        }
        else
        {
            for(int i=0;i<=1;i++)
            {
                if(i==1 && one)
                continue;
                if(i==1)
                count+=solve(n,take-1,0,1,dp);
                else
                count+=solve(n,take-1,0,0,dp);
            }
        }
        return dp[take][tight][one]=count;
    }
    int findIntegers(int n) {
        int take=0;
        while((1<<take) <= n)
        take++;
        take--;
        int ans=0, ind=0;
        vector<vector<vector<int>>> dp(take+1, vector<vector<int>> (2, vector<int> (2,-1)));
        if(n & (1<<take))
        ind=1;
        // cout<<ind<<endl;
        for(int i=0;i<=ind;i++)
        {
            if(i==ind)
            {
                if(i==1)
                ans+=solve(n,take-1,1,1,dp);
                else
                ans+=solve(n,take-1,1,0,dp);
            }
            else
            {
                if(i==1)
                ans+=solve(n,take-1,0,1,dp);
                else
                ans+=solve(n,take-1,0,0,dp);
            }
        }
        return ans;
    }
};
11200