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

&nbsp;
Example 1:

Input: n = 5
Output: 5
Explanation:
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. 


Example 2:

Input: n = 1
Output: 2


Example 3:

Input: n = 2
Output: 3


&nbsp;
Constraints:


	1 &lt;= n &lt;= 109


class Solution:
    def findIntegers(self, n: int) -> int:
        b=(bin(n).replace("0b",""))
        dp=[[[[-1 for i in range(2)] for i in range(2)] for i in range(2)] for i in range(30)]
        def fun(i,last,tight,leading_zeros):
            if i==len(str(b)):
                return 1
            if dp[i][tight][leading_zeros][last]!=-1:
                return dp[i][tight][leading_zeros][last]
            end=1
            if tight==1:
                end = int(b[i])
            res=0
            for j in range(end+1):
                if j==0 and leading_zeros==1:
                    res+=fun(i+1,j,tight&int(j==end),1)
                else:
                    if j==0:
                        res+=fun(i+1,j,tight&int(j==end),0)
                    else:
                        if last!=j:
                            res+=fun(i+1,j,tight&int(j==end),0)
            dp[i][tight][leading_zeros][last] = res
            return res
        return fun(0,0,1,1)
class Solution {
    public int findIntegers(int n) {
        int val=0,res=0,cn=n,digi=0,prevdig=0,i;//digi means bin digi
        while(cn>0){
            cn=cn>>1;
            digi++;
        }
        int dp[]=new int[digi+1];
        dp[0]=1;dp[1]=2;
        for(i=2;i<=digi;i++)
            dp[i]=dp[i-1]+dp[i-2];
        digi++;
        while(digi-->=0){
            if((n&(1<<digi))>0){
                res+=dp[digi];
                if(prevdig==1)return res;
                prevdig=1;
            }else prevdig=0;
        }
        
        return res+1;
    }
}
class Solution {
public:
    int dp[31][2];
    vector<int> f(){ 
        vector<int> res(31, 1);
        dp[1][0]=0;
        dp[1][1]=1;
        for(int i=2; i<31; i++){
            dp[i][0]=dp[i-1][0]+dp[i-1][1];
            dp[i][1]=dp[i-1][0];
        }
        
        
        for(int i=1; i<31; i++){
            res[i]=res[i-1]+dp[i][0]+dp[i][1];
        }

        res[1]=2;
        return res;
    }
    
    int findIntegers(int n) {
        int res=0;
        int bits=0;
        int temp=n;
        vector<int> v;
        while(temp>0){
            bits++;
            v.push_back(temp&1);
            temp=temp>>1;
        }
        vector<int> nums=f();
        
        bool valid=true, isValid=true;

        for(int i=bits-2;i>=0;i--){
            if(v[i]==1 && v[i+1]==1){
                res+=nums[i];
                isValid=false;
                break;
            }else if(v[i]==1)
                res+=nums[i];
        }
        
        res+=nums[bits-1];
        return isValid==true ? res+1:res;
    }
};
var findIntegers = function(n) {
    let dp = len=>{
        if (len<0)
            return 0;
        if (!len)
            return 1;
        let _0x = 1; // number of accepted combination when '1' is first
        let _1x = 1; // number of accepted combination when '0' is first
        while (--len)
            [_0x, _1x] = [_0x+_1x, _0x];
        return _0x + _1x;
    };
    let binary = n.toString(2);
    let count = 0;
    let is_prev_one = false;
    for (let i = 0; i<binary.length; i++) {
        if (binary[i] === '0') {
            is_prev_one = false;
            continue;
        }
        count += dp(binary.length-i-1);
        if (is_prev_one)
            return count;
        is_prev_one = true;
    }
    return count + 1;
};
Non-negative Integers without Consecutive Ones