600. Non-negative Integers without Consecutive Ones

Problem Description

The task is to find the count of integers between 0 and a given positive integer n that do not have consecutive 1s in their binary representation. For example, the number 5 is represented in binary as 101 and does not have consecutive 1s; hence, it should be included in the count. However, the number 6, which is 110 in binary, has consecutive 1s and should not be counted.

Intuition

The intuition behind the solution involves understanding binary numbers and dynamic programming. Each binary number can be thought of as a string of 0s and 1s. To avoid consecutive 1s, we can never place a 1 after another 1 while forming this string.

The solution uses a technique called "Depth First Search" (DFS) to explore all possible valid binary strings up to a certain length and count how many do not have consecutive 1s.

To optimize this approach, memoization (caching the results) is used, which is a common technique in dynamic programming. This prevents the recalculation of the same state multiple times, saving on execution time.

The dynamic programming function dfs takes three parameters:

1. pos: This indicates the current position in the binary representation we are examining.
2. pre: This is the previous digit in the binary representation.
3. limit: This is a boolean which tells us whether we are at the upper limit of our number n or not.

The dfs function works backwards from the most significant bit to the least, trying out digits (0 or 1) at each position, but skipping the placement of a 1 after another 1.

The a array holds the bits of the input number n in reverse order (a[1] is the least significant bit), and l keeps the length of this binary representation. The function dfs is called with the upper limit, and it recursively calculates the valid integers.

The result is the number of valid integers up to n that can be formed without consecutive 1s in binary form.

Learn more about Dynamic Programming patterns.

Solution Approach

The provided solution approach combines Depth First Search (DFS) with dynamic programming and memoization.

Here's how the code works step-by-step:

1. Memoization with @cache: The dfs function is decorated with Python's @cache from functools. This optimization technique stores the results of expensive function calls and returns the cached result when the same inputs occur again. This reduces the number of recalculations for states that have already been computed.

2. The dfs function: The recursive function dfs checks all possible binary numbers from n to 0. It takes three arguments as described earlier (pos, pre, and limit):

   • pos: The current bit position we're trying to fill.
   • pre: The previous bit's value (0 or 1) to check for consecutive ones.
   • limit: A boolean indicating if the number being formed should be less than or equal to n.

   The base case of our recursion is when pos <= 0, wherein we return 1 to denote a single valid number has been counted.

   For each recursive call of dfs, we determine the possible values for the current bit, based on limit and the corresponding bit in the number n. We then loop through the possible choices (0 or 1) for the current position, making sure not to put a 1 after another 1 (if pre == 1 and i == 1: continue). If a valid digit is chosen, dfs proceeds to the next position.

   The ans += dfs(pos - 1, i, limit and i == up) line accumulates the count of valid integers by moving to the next bit position, updating the previous bit to the current bit value (i) and determining if we are still constrained by the limit.

3. Preparing the input for DFS: Prior to calling dfs, the binary representation of n is stored in reverse order in the array a, and l is set to the length of this binary representation. This sets up a way to easily access the value of each binary digit while enforcing the limit condition in the DFS algorithm.

4. Performing the DFS: Finally, dfs is called with the length of the binary representation, an initial previous bit value of 0 (since there is no digit before the first one), and a limit of True, indicating that the number being formed must not exceed n. The recursion explores all valid binary numbers, taking into account the absence of consecutive ones, within the given boundary.

The solution efficiently traverses the space of all potential binary numbers up to n without encountering consecutive ones and returns the total count of such numbers. Utilizing both DFS and memoization, the algorithm ensures that every valid number configuration is counted exactly once in an optimized manner.

Example Walkthrough

Let's illustrate the solution approach with an example where n = 5. The binary representation of 5 is 101, which does not have consecutive 1s.

Step 1: Convert n to its binary representation and store it in an array a in reverse order.

• For n = 5, the binary representation is 101.
• Reverse it to get a = [1,0,1], and set l = 3 since there are three bits in the binary representation.

Step 2: Call the dfs function initially with dfs(l, 0, True).

• pos starts at l = 3, which represents the most significant bit (MSB).
• pre is 0, since there is no bit before the MSB.
• limit is True, as we must remain within the bounds of n.

Step 3: Inside dfs(pos, pre, limit), execute the recursion:

• First Call: dfs(3, 0, True):
  • Since pos is not <= 0, continue with the function.
  • Determine the highest bit we can use: up = a[pos] if limit is True, else 1. Since limit is true now, up = a[3] = 1.
  • Loop over the possible binary digits at this position (0 and 1), with i being the current digit.
    • If pre is 1 (which it isn't in this call) and i is 1, we continue to the next iteration to avoid consecutive 1s.
    • Recur with dfs(pos - 1, i, limit and i == up).
      • For i = 0: dfs(2, 0, False) – the limit becomes False since i is not equal to up.
      • For i = 1: dfs(2, 1, True) – we still respect the upper limit since i equals up.
• Recursive calls proceed, exploring all combinations and appending to ans if no consecutive 1s are present.

Step 4: Continue recursion until pos <= 0, which means a valid number has been formed:

• For example, when calling with dfs(0, some_pre, some_limit), return 1 signifying a valid number count.

Step 5: Exit recursion with the sum of all ans values obtained.

Example Calculations:

• dfs(3, 0, True) calls dfs(2, 0, False) and dfs(2, 1, True)
  • dfs(2, 0, False) calls dfs(1, 0, False) (valid path) and dfs(1, 1, False) (valid path)
    • dfs(1, 0, False) calls dfs(0, 0, False) and dfs(0, 1, False) – each returns 1 since these are valid, totaling 2.
    • dfs(1, 1, False) calls dfs(0, 0, False) only (since dfs(0, 1, False) would have consecutive 1s) – returns 1.
  • dfs(2, 1, True) calls dfs(1, 0, False) (valid path)
    • dfs(1, 0, False) again calls dfs(0, 0, False) and dfs(0, 1, False) – each returns 1, totaling 2.

Summing the paths: We get 2 (from dfs(2, 0, False)) + 1 (from dfs(2, 1, True)) + 2 (from dfs(1, 0, False) within dfs(2, 1, True)), which gives us a result of 5 valid integers.

The valid integers between 0 and 5 that don't have consecutive 1s in binary form are: 0 (0), 1 (1), 2 (10), 4 (100), and 5 (101). The count is 5, which matches our calculated result.

The memoization helps avoid recalculating the same states, effectively optimizing the process. This example demonstrates with simplified numbers how the DFS and dynamic programming approach work together to solve the problem.

Solution Implementation

Time and Space Complexity

The given Python code defines a method findIntegers to calculate the number of non-negative integers less than or equal to n that do not contain consecutive ones in their binary representation.

Time Complexity

The time complexity of the solution revolves around the depth-first search function dfs, which uses memoization (through the @cache decorator) to avoid recalculating the same state.

The function dfs runs for each bit position of the given number n - there are a maximum of O(log n) bits in n.

At each bit position, there are two possibilities for pre (0 or 1), and there are up to two choices to consider for the current bit (also 0 or 1). However, the 'limit' flag constrains the recursion based on whether the current bit sequence is strictly less than n or at the upper limit of n. Thus, at most, there are 2 * 2 = 4 recursive calls for each bit position, but due to memoization and the limit flag's pruning, not all of these calls will be fully executed.

Furthermore, due to the memoization and the constraints imposed by 'limit' and consecutive ones not being allowed (if pre == 1 and i == 1: continue), the actual number of states will be significantly less than the maximum possible states.

Hence, the time complexity of dfs is O(2*log n), where two states pre and limit iterate over log n bits. Since each state is calculated only once, this gives a total time complexity of O(log n).

Space Complexity

The space complexity of the solution involves the space used by the memoization cache and the auxiliary stack space used by the recursive calls. As memoization stores a result for each unique state explored during the execution, and there can be at most O(log n) levels of recursion with 2 states for pre and two states for limit, the space used by the cache is O(log n).

Similarly, the call stack's maximum depth will be O(log n) because the recursion goes as deep as the number of bits in n.

Therefore, the overall space complexity of the code is O(log n) for both the memoization cache and the call stack.

Learn more about how to find time and space complexity quickly using problem constraints.