Last updated on October 9th, 2024 at 06:12 pm

Here, We see Non-negative Integers without Consecutive Ones LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Non-negative Integers without Consecutive Ones LeetCode Solution

Problem Statement

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

Example 1:
Input: n = 5
Output: 5
Explanation: Here are the non-negative integers <= 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

1. Non-negative Integers without Consecutive Ones LeetCode Solution C++

class Solution {
public:
    int findIntegers(int n) {
         if(n == 0) return 1;
         if(n == 1) return 2;         
         int digit = 0;
         while(n >= 1 << digit) digit++;
         int *digitsOfNum = new int[digit];
         int *zero = new int[digit];
         int *one = new int[digit];
         zero[0] = 0;
         zero[1] = 1;
         one[0] = 1;
         one[1] = 0;
         int sum = 1; //include 0
         for(int i = 0; i < digit; i++)
         {
             if(i > 1) 
             {
                 zero[i] = zero[i - 1] + zero[i - 2];
                 one[i] = one[i - 1] + one[i - 2];
             }
             if(i < digit - 1) sum += zero[i] + one[i];
             digitsOfNum[digit - 1 - i] = n % 2;
             n >>= 1;
         }
        
         int i = 0;
         bool isValid = true;
         while(true)
         {
             if(i + 1 == digit)break;
             if(isValid)
             {
                 if(digitsOfNum[i] != digitsOfNum[i + 1])
                 {
                     zero[i + 1] = zero[i] + one[i];
                     one[i + 1] = zero[i];
                     i++;
                 }else{
                     if(digitsOfNum[i] == 1)
                     {
                         isValid = false;
                     }else{
                         zero[i + 1] = zero[i] + one[i];
                         one[i + 1] = zero[i] - 1;
                         i++;
                     }
                 }
             }else{
                 zero[i + 1] = zero[i] + one[i];
                 one[i + 1] = zero[i];
                 i++;
             }
         }
         return sum + zero[digit - 1] + one[digit - 1];
    }
};

2. Non-negative Integers without Consecutive Ones LeetCode Solution Java

class Solution {
    public int findIntegers(int n) {
        String binary = Integer.toBinaryString(n);
        int k = binary.length();

        int[] fib = new int[k+1];
        fib[0] = 1;
        fib[1] = 2;
        for(int i=2;i<=k;i++){
            fib[i] = fib[i-1]+fib[i-2];
        }
        
        boolean isLastBitOne = false;
        int res=0;
        int bit = k-1;
        while(bit>=0){
            if((n & (1<<bit))==0){
                isLastBitOne=false;
            } else {
                res+=fib[bit];
                if(isLastBitOne){
                    return res;
                }
                isLastBitOne=true;
            }
            bit--;
        }
        
        return res+1;
    }
}

3. Non-negative Integers without Consecutive Ones Solution JavaScript

var findIntegers = function (n) {
    let s = n.toString(2);
    n = s.length;
    let dp0 = 1, dp1 = 0, tight = 1;
    for (let i = 1; i < n; i++) {
        let xdp0 = dp1 + dp0;
        let xdp1 = dp0;
        if (tight && s[i] === '1') {
            xdp0++;
            if (s[i - 1] === '1') tight = 0;
        }
        dp0 = xdp0;
        dp1 = xdp1;
    }
    return dp0 + dp1 + tight;
};

4. Non-negative Integers without Consecutive Ones Solution Python

class Solution(object):
    def findIntegers(self, n):
        f = [1, 2]
        for i in range(2, 30):
            f.append(f[-1]+f[-2])
        
        ans, last_seen = 0, 0
        for i in reversed(range(30)):
            if (1 << i) & n: # is the ith bit set?
                ans += f[i]
                if last_seen: 
                    ans -= 1
                    break
                last_seen = 1
            else:
                last_seen = 0
        return ans+1