600. Non-negative Integers without Consecutive Ones LeetCode Solution
In this guide, you will get 600. Non-negative Integers without Consecutive Ones LeetCode Solution with the best time and space complexity. The solution to Non-negative Integers without Consecutive Ones problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Non-negative Integers without Consecutive Ones
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
Constraints:
1 <= n <= 109
Complexity Analysis
Time Complexity: O(\log n)
Space Complexity: O(\log n)
600. Non-negative Integers without Consecutive Ones LeetCode Solution in C++
class Solution {
public:
int findIntegers(int num) {
string bits;
for (; num; num >>= 1)
bits += to_string(num & 1);
const int n = bits.length();
vector<int> zero(n, 1);
vector<int> one(n, 1);
for (int i = 1; i < n; ++i) {
zero[i] = zero[i - 1] + one[i - 1];
one[i] = zero[i - 1];
}
int ans = zero[n - 1] + one[n - 1];
for (int i = n - 2; i >= 0; --i) {
// The numbers > num and <= 2^n - 1 are invalid.
if (bits[i] == '1' && bits[i + 1] == '1')
break;
if (bits[i] == '0' && bits[i + 1] == '0')
ans -= one[i];
}
return ans;
}
}; /* code provided by PROGIEZ */
600. Non-negative Integers without Consecutive Ones LeetCode Solution in Java
class Solution {
public int findIntegers(int num) {
StringBuilder bits = new StringBuilder();
for (; num > 0; num >>= 1)
bits.append(num & 1);
final int n = bits.length();
int[] zero = new int[n];
int[] one = new int[n];
zero[0] = 1;
one[0] = 1;
for (int i = 1; i < n; ++i) {
zero[i] = zero[i - 1] + one[i - 1];
one[i] = zero[i - 1];
}
int ans = zero[n - 1] + one[n - 1];
for (int i = n - 2; i >= 0; --i) {
// The numbers > num and <= 2^n - 1 are invalid.
if (bits.charAt(i) == '1' && bits.charAt(i + 1) == '1')
break;
if (bits.charAt(i) == '0' && bits.charAt(i + 1) == '0')
ans -= one[i];
}
return ans;
}
} // code provided by PROGIEZ
600. Non-negative Integers without Consecutive Ones LeetCode Solution in Python
