# Non-negative Integers without Consecutive Ones **Difficulty:** HARD [External](https://leetcode.com/problems/non-negative-integers-without-consecutive-ones) Canonical: https://scaleengineer.com/dsa/problems/non-negative-integers-without-consecutive-ones **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Companies:** [Pocket Gems](https://scaleengineer.com/companies/pocket-gems) --- ## Problem 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` # Approaches ## Brute Force Iteration 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`. **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) **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 of `n <= 10^9`. ### Explanation 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. ```java 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; } } ``` ### Algorithm - Initialize a counter `count` to 0. - Iterate through each integer `i` from 0 to `n`. - 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 `i` does not have consecutive ones, increment the `count`. - After the loop finishes, return `count`. ## Dynamic Programming with Memoization (Digit DP) A much more efficient method is to use dynamic programming, specifically a technique often called 'Digit DP'. Instead of checking every number, we build the valid numbers digit by digit (or bit by bit in this case) and count how many can be formed that are less than or equal to `n`. This avoids the linear scan and reduces the complexity logarithmically. **Time:** O(log n). The number of states in our DP is `length * 2 * 2`, where `length` is the number of bits in `n`, which is `O(log n)`. Each state is computed once. · **Space:** O(log n) for the memoization table and recursion stack depth. The number of bits in `n` is `log n`. **Pros:** Extremely efficient with logarithmic time complexity.; A generalizable technique for a wide range of 'digit'-based counting problems. **Cons:** The recursive nature and the concept of the 'tight' constraint can be slightly complex to grasp for beginners. ### Explanation The core idea is to count the valid numbers by constructing them from the most significant bit to the least significant bit. We define a recursive function with memoization to count the number of ways to fill the remaining bits of a number, given a certain prefix. The state of our DP needs to capture all the necessary information to make decisions for the subsequent bits. This includes: 1. `index`: The current bit position we are considering. 2. `tight`: A constraint flag. If the prefix we've built so far is identical to the prefix of `n`, then for the current `index`, we can only choose a bit up to `n`'s bit at that `index`. If our prefix is already smaller, we are no longer 'tightly' constrained and can choose any bit (0 or 1). 3. `prevIsOne`: A flag to remember if the immediate preceding bit was a 1, to enforce the no-consecutive-ones rule. By memoizing the results for each state `(index, tight, prevIsOne)`, we avoid recomputing the same subproblems, leading to a very efficient solution. ```java import java.util.Arrays; class Solution { int[][][] memo; String s; public int findIntegers(int n) { s = Integer.toBinaryString(n); memo = new int[s.length()][2][2]; for (int[][] arr2D : memo) { for (int[] arr1D : arr2D) { Arrays.fill(arr1D, -1); } } // solve(index, tight_constraint, previous_bit_is_one) return solve(0, 1, 0); } private int solve(int index, int tight, int prevIsOne) { if (index == s.length()) { return 1; // Found a valid number } if (memo[index][tight][prevIsOne] != -1) { return memo[index][tight][prevIsOne]; } int ans = 0; int upperBound = (tight == 1) ? (s.charAt(index) - '0') : 1; for (int digit = 0; digit <= upperBound; digit++) { if (prevIsOne == 1 && digit == 1) { continue; // Avoid consecutive ones } // The new tight constraint is true only if the old one was true // AND we are placing the maximum possible digit. int newTight = (tight == 1 && digit == upperBound) ? 1 : 0; ans += solve(index + 1, newTight, digit); } return memo[index][tight][prevIsOne] = ans; } } ``` ### Algorithm - Convert the input integer `n` into its binary string representation, let's call it `s`. - Create a recursive function, say `solve(index, tight, prevIsOne)`, which counts the number of valid ways to complete a number from a given state. - The state is defined by: - `index`: The current bit position we are filling (from left to right). - `tight`: A boolean (or integer 0/1) flag. It's true if we are restricted to the digits of `n`'s binary string `s` (i.e., we've matched the prefix of `s` so far). If false, we can use any digit (0 or 1). - `prevIsOne`: A boolean (or integer 0/1) flag, true if the previously placed bit was a 1. - Use a memoization table (e.g., a 3D array `memo[index][tight][prevIsOne]`) to store the results of subproblems. - The base case for the recursion is when `index` reaches the end of the string `s`, meaning we have successfully formed one valid number. In this case, return 1. - In the recursive step, iterate through the possible digits `d` for the current `index`. The upper bound for `d` is `s[index]` if `tight` is true, otherwise it's 1. - If `prevIsOne` is true, we cannot place a `1`. So, we skip `d=1`. - For each valid `d`, make a recursive call `solve(index + 1, newTight, newPrevIsOne)` and add the result to the total count. The `newTight` flag will be true only if the original `tight` was true and we chose the maximum possible digit `d`. - The initial call to the function would be `solve(0, true, false)`. ## Iterative Approach with Fibonacci Numbers This approach builds upon the dynamic programming idea but uses a direct combinatorial insight related to the Fibonacci sequence. It provides an iterative and highly optimized solution by precomputing the number of valid binary strings of different lengths. **Time:** O(log n). We perform a single pass over the bits of `n`, and the precomputation also takes `O(log n)` time. · **Space:** O(log n) to store the Fibonacci numbers. The length of the binary string is `O(log n)`. **Pros:** The most efficient approach with O(log n) complexity.; Iterative solution, which can be slightly faster in practice than a recursive one due to avoiding recursion overhead.; Reveals an elegant mathematical property of the problem. **Cons:** The connection to Fibonacci numbers might not be immediately obvious, making the logic seem magical at first. ### Explanation The key observation is that the count of non-negative integers without consecutive ones for a given number of bits relates to the Fibonacci sequence. Let `f[i]` be the number of valid binary strings of length `i`. - `f[0] = 1` (the empty string) - `f[1] = 2` ("0", "1") - `f[2] = 3` ("00", "01", "10") - `f[3] = 5` ("000", "001", "010", "100", "101") This sequence is `f[i] = f[i-1] + f[i-2]`, which is the Fibonacci sequence (shifted). We can leverage this to count the valid numbers up to `n`. We scan the binary representation of `n` from the most significant bit. At each bit `i`, if `n` has a '1', we can calculate how many valid numbers could have been formed by placing a '0' at that bit instead. The number of ways to complete the number from there is simply `f[k]` where `k` is the number of remaining bits. We add this to our total. If we encounter consecutive '1's in `n`'s binary string, we stop early, as `n` and any number with that prefix would be invalid. Finally, if `n` itself is a valid number, we add it to the count. ```java class Solution { public int findIntegers(int n) { String s = Integer.toBinaryString(n); int len = s.length(); // f[i] = number of valid binary strings of length i int[] f = new int[len + 1]; f[0] = 1; f[1] = 2; for (int i = 2; i <= len; i++) { f[i] = f[i - 1] + f[i - 2]; } int count = 0; int prevBit = 0; for (int i = 0; i < len; i++) { int bit = s.charAt(i) - '0'; if (bit == 1) { // If we place a '0' at this position, any valid combination // for the remaining bits is allowed. The number of remaining // bits is (len - 1 - i). count += f[len - 1 - i]; if (prevBit == 1) { // Found '11' in n's binary representation. // All numbers with this prefix are invalid, including n. // The count we have is for numbers < n. So, we can return. return count; } } prevBit = bit; } // The loop counted all valid numbers < n. // Since the loop finished without returning, n itself is valid. return count + 1; } } ``` ### Algorithm - First, observe that the number of binary strings of length `k` without consecutive ones follows the Fibonacci sequence. Let `f[k]` be this count. We have `f[0] = 1` (empty string), `f[1] = 2` ('0', '1'), and `f[k] = f[k-1] + f[k-2]`. This is because a valid string of length `k` can be formed by appending '0' to any valid string of length `k-1`, or by appending '1' to a valid string of length `k-1` that ends in '0' (which is equivalent to any valid string of length `k-2` followed by '0'). - Precompute these Fibonacci-like numbers up to the number of bits in `n`. - Convert `n` to its binary string `s` of length `L`. - Initialize `count = 0` and a flag `prevBit = 0`. - Iterate through the bits of `s` from left to right (from index `i = 0` to `L-1`). - If the current bit `s[i]` is '1': - We can form valid numbers by placing a '0' at this position. The number of ways to fill the remaining `L-1-i` bits is `f[L-1-i]`. Add this to `count`. - If the previous bit (`s[i-1]`) was also '1', it means `n` itself (and any number with this prefix) has consecutive ones. We have already counted all valid numbers strictly smaller than `n`, so we can stop and return the current `count`. - Update `prevBit` to the current bit's value. - If the loop completes, it means `n` itself does not have consecutive ones. The `count` currently holds the number of valid integers strictly less than `n`. So, we add 1 to include `n` itself. - Return the final `count`. # Solutions ### Java ```java 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; } } ``` ### CPP ```cpp class Solution { public: int a[33]; int dp[33][2]; int findIntegers(int n) { int len = 0; while (n) { a[++len] = n & 1; n >>= 1; } memset(dp, -1, sizeof dp); return dfs(len, 0, true); } int dfs(int pos, int pre, bool limit) { if (pos <= 0) { return 1; } if (!limit && dp[pos][pre] != -1) { return dp[pos][pre]; } int ans = 0; int up = limit ? a[pos] : 1; 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; } }; ``` ### Python ```python class Solution: def findIntegers(self, n: int) -> int: @ cache def dfs(pos, pre, limit): if pos <= 0: return 1 up = a[pos] if limit else 1 ans = 0 for i in range(up + 1): if pre == 1 and i == 1: continue ans += dfs(pos - 1, i, limit and i == up) return ans a = [0] * 33 l = 0 while n: l += 1 a[l] = n & 1 n >>= 1 return dfs(l, 0, True) ```