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](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
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
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];
}
};
Code language: PHP (php)
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;
}
}
Code language: JavaScript (javascript)
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;
};
Code language: JavaScript (javascript)
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