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*

*List of all LeetCode Solution*

## Topics

Dynamic Programming

## Level of Question

Hard

**Non-negative Integers without Consecutive Ones LeetCode Solution**

## Table of Contents

**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