Solution Explanation: Non-negative Integers without Consecutive Ones

This problem requires finding the count of non-negative integers up to a given integer n whose binary representations don't contain consecutive 1s. The most efficient approach is using dynamic programming (specifically, digit DP).

Core Idea:

The solution leverages a recursive approach with memoization to avoid redundant calculations. The key is to consider the binary representation of numbers and build the solution digit by digit.

dfs(i, pre, limit) Function:

The recursive function dfs(i, pre, limit) takes three arguments:

• i: The current bit position (starting from the most significant bit, i.e., the leftmost bit).
• pre: The value of the previous bit (0 or 1). This helps to track whether consecutive 1s are present.
• limit: A boolean flag indicating whether the current bit is constrained by the input number n. If limit is true, it means the current bit cannot exceed the corresponding bit in n.

Base Case:

If i is less than 0, it implies that all bits have been processed, and a valid number without consecutive 1s has been found. The function returns 1 (counting this valid number).

Recursive Step:

The function iterates through possible values for the current bit j (0 or 1, or up to the value of the corresponding bit in n if limit is true).

• Consecutive 1 Check: If pre and j are both 1, it means consecutive 1s are present, so this combination is skipped.
• Recursive Call: Otherwise, a recursive call dfs(i - 1, j, limit and j == up) is made to process the next bit. The limit flag is updated to ensure constraints are followed.
• Result Aggregation: The results from all valid combinations are summed up.

Memoization:

The @cache decorator (in Python) or the f array (in Java, C++, Go, TypeScript) acts as a memoization table to store the results of subproblems, preventing redundant computations.

Time and Space Complexity:

• Time Complexity: O(log n). The recursion depth is proportional to the number of bits in n, which is log₂(n). Memoization ensures that each subproblem is solved only once.
• Space Complexity: O(log n) for the recursion stack and the memoization table.

Code Examples (with detailed comments):

The provided code demonstrates the solution in several languages (Python, Java, C++, Go, TypeScript). The logic remains consistent across all languages; only syntax differs. Refer to the comments in each code snippet for a clear understanding.

Example (Python):

class Solution:
    def findIntegers(self, n: int) -> int:
        @lru_cache(None)  # Memoization decorator
        def dfs(i: int, pre: int, limit: bool) -> int:
            if i < 0:  # Base case: all bits processed
                return 1
            up = (n >> i & 1) if limit else 1  # Determine the upper bound for the current bit
            ans = 0
            for j in range(up + 1):
                if pre and j:  # Skip if consecutive 1s
                    continue
                ans += dfs(i - 1, j, limit and j == up) # Recursive call
            return ans
 
        return dfs(n.bit_length() - 1, 0, True) # Start recursion from the most significant bit
 

The other languages follow a very similar structure, using appropriate memoization techniques. The core recursive logic and base case remain the same.