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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

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

1from functools import lru_cache  # This is used to cache the results of the function calls.
2
3class Solution:
4    def findIntegers(self, n: int) -> int:
5        # Helper function that uses Depth-First Search (DFS) to find the count of valid integers.
6        @lru_cache(maxsize=None)  # This decorator caches the results of the function.
7        def dfs(position, previous_digit, is_limited):
8            # Base case: if the current position is less than or equal to 0, return 1.
9            if position <= 0:
10                return 1
11
12            # Determine the upper bound to loop over based on whether we're limited by the input number.
13            upper_bound = binary_representation[position] if is_limited else 1
14
15            # Initialize the count of valid integers.
16            count = 0
17
18            # Iterate over possible digits (0 or 1) at the current position.
19            for digit in range(upper_bound + 1):
20                # Skip the iteration if the previous and current digits are both 1,
21                # because it's not allowed to have two consecutive 1s.
22                if previous_digit == 1 and digit == 1:
23                    continue
24
25                # Accumulate the count by recursively calling dfs for the next position.
26                # The is_limited flag is updated depending on if the current digit reaches the upper bound.
27                count += dfs(position - 1, digit, is_limited and digit == upper_bound)
28
29            # Return the total count of valid integers for this branch.
30            return count
31
32        # Convert the input number to a binary representation (in reverse order).
33        binary_representation = [0] * 33  # Initialize an array to hold the binary digits.
34        length = 0  # Length of the binary representation.
35        while n:
36            length += 1
37            binary_representation[length] = n & 1  # Extract the last binary digit.
38            n >>= 1  # Right shift the number by 1 to process the next digit.
39
40        # Call the DFS function starting from the highest position (most significant bit),
41        # with the previous digit being 0 and setting the is_limited flag to True.
42        return dfs(length, 0, True)
43
1class Solution {
2    // The 'a' array will hold the binary representation of the number.
3    private int[] binaryArray = new int[33];
4    // The 'dp' array is used for memoization to store intermediate results.
5    private int[][] dp = new int[33][2];
6
7    // This method finds the total count of non-negative integers less than or equal to n 
8    // which do not have consecutive ones in their binary representation.
9    public int findIntegers(int n) {
10        // 'len' will hold the length of the binary representation of 'n'.
11        int len = 0;
12        // Converting the number 'n' to binary and storing it in 'binaryArray'.
13        while (n > 0) {
14            binaryArray[++len] = n & 1; // Storing the least significant bit.
15            n >>= 1; // Right shift 'n' by 1 bit to process the next bit.
16        }
17        // Initialize all elements of 'dp' array to -1 to indicate uncomputed states.
18        for (int[] row : dp) {
19            Arrays.fill(row, -1);
20        }
21        // Start the depth-first search (DFS) from the most significant bit.
22        return dfs(len, 0, true);
23    }
24
25    // The 'dfs' method computes the count recursively using memoization.
26    private int dfs(int pos, int prevBitSet, boolean isLimit) {
27        // Base case: when there are no more bits to process, return 1 as a single 
28        // number (considered as 0) does not have consecutive ones.
29        if (pos <= 0) {
30            return 1;
31        }
32        // If the current state is not limited by the input number's bits and 
33        // a value is already computed for the state 'dp[pos][prevBitSet]', return it.
34        if (!isLimit && dp[pos][prevBitSet] != -1) {
35            return dp[pos][prevBitSet];
36        }
37        // Determine the upper limit of the current bit. If 'isLimit' is true,
38        // the current bit cannot exceed the bit in the input number's binary representation.
39        int upperLimit = isLimit ? binaryArray[pos] : 1;
40        // Initialize the count of valid integers for the current position to 0.
41        int count = 0;
42        // Explore both possible states for the current bit (0 or 1),
43        // but skip the state where both the current and previous bits are 1.
44        for (int i = 0; i <= upperLimit; ++i) {
45            if (!(prevBitSet == 1 && i == 1)) { // Check for no consecutive ones.
46                count += dfs(pos - 1, i, isLimit && i == upperLimit);
47            }
48        }
49        // If the current state is not limited, store the computed value for reuse.
50        if (!isLimit) {
51            dp[pos][prevBitSet] = count;
52        }
53        // Return the total count of valid integers for the current position.
54        return count;
55    }
56}
57
1class Solution {
2public:
3    // Array to store individual bits.
4    int bits[33];
5
6    // DP array to memoize the results of subproblems.
7    int memo[33][2];
8
9    // Function to find the number of non-negative integers less than or equal to n with no consecutive ones in their binary representation.
10    int findIntegers(int n) {
11        // Initialize variable to represent the length of the binary representation of n.
12        int length = 0;
13
14        // Convert n to binary and store it in the array bits in reverse order.
15        while (n) {
16            bits[++length] = n & 1;
17            n >>= 1;
18        }
19
20        // Initialize memo array with -1 to indicate uncomputed subproblems.
21        memset(memo, -1, sizeof memo);
22
23        // Use depth-first search to calculate the answer, starting from the most significant bit.
24        return dfs(length, 0, true);
25    }
26
27    // DFS function to solve the problem.
28    int dfs(int pos, int prev, bool limit) {
29        // Base case: when position is 0, there is only one number, which is 0.
30        if (pos <= 0) {
31            return 1;
32        }
33
34        // If not in limit and result is already computed, return it.
35        if (!limit && memo[pos][prev] != -1) {
36            return memo[pos][prev];
37        }
38
39        // Initialize the answer for the current state.
40        int ans = 0;
41
42        // Determine the upper limit for the current bit. It's either 1 or the actual bit value if we're at the limit.
43        int upperBound = limit ? bits[pos] : 1;
44
45        // Iterate through all possible values of the current bit (0 or 1).
46        for (int i = 0; i <= upperBound; ++i) {
47            // If the previous bit wasn't 1 or the current bit isn't 1, continue exploring further.
48            if (!(prev == 1 && i == 1)) {
49                ans += dfs(pos - 1, i, limit && i == upperBound); // Add the result from the subproblem.
50            }
51        }
52
53        // If the current state is not at the limit, memoize the result.
54        if (!limit) {
55            memo[pos][prev] = ans;
56        }
57
58        // Return the answer for the current state.
59        return ans;
60    }
61};
62
1// Array to store individual bits.
2let bits: number[] = new Array(33).fill(0);
3
4// DP array to memoize the results of subproblems.
5let memo: number[][] = Array.from({ length: 33 }, () => Array(2).fill(-1));
6
7// Function to find the number of non-negative integers less than or equal to n with no consecutive ones in their binary representation.
8function findIntegers(n: number): number {
9    // Initialize variable to represent the length of the binary representation of n.
10    let length = 0;
11
12    // Convert n to binary and store it in the array bits in reverse order.
13    while (n > 0) {
14        bits[++length] = n & 1;
15        n >>= 1;
16    }
17
18    // Use depth-first search to calculate the answer, starting from the most significant bit.
19    return dfs(length, 0, true);
20}
21
22// DFS function to solve the problem.
23function dfs(pos: number, prev: number, limit: boolean): number {
24    // Base case: when position is 0, there is only one number, which is 0.
25    if (pos === 0) {
26        return 1;
27    }
28
29    // If not in limit and result is already computed, return it.
30    if (!limit && memo[pos][prev] !== -1) {
31        return memo[pos][prev];
32    }
33
34    // Initialize the answer for the current state.
35    let ans = 0;
36
37    // Determine the upper limit for the current bit. It's either 1 or the actual bit value if we're at the limit.
38    let upperBound = limit ? bits[pos] : 1;
39
40    // Iterate through all possible values of the current bit (0 or 1).
41    for (let i = 0; i <= upperBound; i++) {
42        // If the previous bit wasn't 1 or the current bit isn't 1, continue exploring further.
43        if (!(prev === 1 && i === 1)) {
44            ans += dfs(pos - 1, i, limit && i === upperBound); // Add the result from the subproblem.
45        }
46    }
47
48    // If the current state is not at the limit, memoize the result.
49    if (!limit) {
50        memo[pos][prev] = ans;
51    }
52
53    // Return the answer for the current state.
54    return ans;
55}
56

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.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄