<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 binary_expo(int n , int k){
        if (k==0){
            return 1 ; 
        }

        if (k==1){
            return n ; 
        }

        int r = binary_expo(n , k/2) * binary_expo(n , k/2) ; 

        if (k % 2==1){
            r = r*n ; 
        }

        return r ; 
    }
    int findIntegers(int n) {
        map<int , int> m ; 
        vector<int>dp (32) ;


        m[0] =  0 ; 
        dp[0] = 0 ; 

        for(int j=1 ; j<32 ; j++){

            int sum = 0 ; 

            for(int i =0 ; i<j ; i++){
                sum += m[i] ; 
            }
            dp[j] = sum ; 

            sum = binary_expo(2 , j-1) ; 

            for(int i=j-2 ; i>=0 ; i--){
                sum += m[i] ; 
            }

            m[j] = sum ; 
        } 

        cout<<m[1]<<endl ; 
        cout<<dp[2]<<endl ; 

        int ans  = 0 ; 

        vector<int> vec; 

        int x = n ; 

        for(int j = 0 ; j<32 ; j++){
            if (n & 1){
                vec.push_back(j) ; 
            }
            n = n>>1 ; 
        }

        bool found = false  ; 
        int num = 0 ; 
        int count_extra = 0 ; 

        reverse(vec.begin() , vec.end()) ; 

        for(int j=0 ; j<vec.size() ; j++){
            cout<<vec[j]<<' ' ; 
            num += binary_expo(2 , vec[j]) ; 
            ans+= dp[vec[j]] ; 

            if (j>0 && vec[j] == vec[j-1] -1){
                found = true ; 
                count_extra = x - num +1 ; 
                break ; 
            }

            
            
        }

        cout<<count_extra<<endl ; 

        
        
        if (!found ){
            return x+1 -ans ; 
        }
        return x+1 - (ans + count_extra) ; 


    }
};
12100