Non-negative Integers without Consecutive Ones
HardPrompt
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: 2Example 3:
Input: n = 2
Output: 3
Constraints:
1 <= n <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to iterate through every number from 0 to n and, for each number, check if its binary representation contains consecutive ones. If it doesn't, we increment a counter. This method is easy to understand but inefficient for large values of n.
Algorithm
- Initialize a counter
countto 0. - Iterate through each integer
ifrom 0 ton. - For each integer
i, check if its binary representation contains consecutive ones. - A simple way to check this is using bit manipulation. If
(i & (i >> 1))is non-zero, it means there was at least one position where a bit and its adjacent bit to the right were both 1. - If
idoes not have consecutive ones, increment thecount. - After the loop finishes, return
count.
Walkthrough
This approach involves a simple loop from 0 to n. Inside the loop, for each number i, we perform a check. The check for consecutive ones can be done by converting the number to a binary string and searching for the substring "11", but a more efficient bitwise trick exists. By taking the number i and bitwise ANDing it with itself right-shifted by one (i >> 1), we can detect consecutive ones. If the result of i & (i >> 1) is not zero, it implies that there was some bit position k where both the k-th bit and (k-1)-th bit were 1, indicating consecutive ones. While the check for each number is very fast (O(1)), the overall algorithm's performance is limited by the loop that runs n+1 times.
class Solution { public int findIntegers(int n) { int count = 0; for (int i = 0; i <= n; i++) { // Check for consecutive ones using a bitwise trick. // If (i & (i >> 1)) is non-zero, it means there was a '11' pattern. if ((i & (i >> 1)) == 0) { count++; } } return count; }}Complexity
Time
O(n). The loop runs `n+1` times, and the check inside is a constant time operation. This will result in a Time Limit Exceeded error for large `n`.
Space
O(1)
Trade-offs
Pros
Very simple to understand and implement.
Requires minimal space.
Cons
The time complexity is directly proportional to
n, which is too slow for the given constraint ofn <= 10^9.
Solutions
Solution
class Solution {private int[] a = new int[33];private int[][] dp = new int[33][2];public int findIntegers(int n) { int len = 0; while (n > 0) { a[++len] = n & 1; n >>= 1; } for (var e : dp) { Arrays.fill(e, -1); } return dfs(len, 0, true); }private int dfs(int pos, int pre, boolean limit) { if (pos <= 0) { return 1; } if (!limit && dp[pos][pre] != -1) { return dp[pos][pre]; } int up = limit ? a[pos] : 1; int ans = 0; for (int i = 0; i <= up; ++i) { if (!(pre == 1 && i == 1)) { ans += dfs(pos - 1, i, limit && i == up); } } if (!limit) { dp[pos][pre] = ans; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.