Last updated on January 29th, 2025 at 02:12 am
Here, we see a Non-negative Integers without Consecutive Ones LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Level of Question
Hard
Non-negative Integers without Consecutive Ones LeetCode Solution
Table of Contents
1. 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
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Fibonacci Numbers with Bit Manipulation. This pattern is based on the Fibonacci sequence and bitwise operations to solve the problem of finding integers without consecutive 1s in their binary representation.
3. Code Implementation in Different Languages
3.1 Non-negative Integers without Consecutive Ones 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];
}
};
3.2 Non-negative Integers without Consecutive Ones 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.3 Non-negative Integers without Consecutive Ones 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;
};
3.4 Non-negative Integers without Consecutive Ones 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
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(log n) | O(log n) |
| Java | O(log n) | O(log n) |
| JavaScript | O(log n) | O(log n) |
| Python | O(log n) | O(log n) |