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:
pos
: This indicates the current position in the binary representation we are examining.pre
: This is the previous digit in the binary representation.limit
: This is a boolean which tells us whether we are at the upper limit of our numbern
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:
-
Memoization with
@cache
: Thedfs
function is decorated with Python's@cache
fromfunctools
. 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. -
The
dfs
function: The recursive functiondfs
checks all possible binary numbers fromn
to 0. It takes three arguments as described earlier (pos
,pre
, andlimit
):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 ton
.
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 onlimit
and the corresponding bit in the numbern
. 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 thelimit
. -
Preparing the input for DFS: Prior to calling
dfs
, the binary representation ofn
is stored in reverse order in the arraya
, andl
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. -
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 alimit
ofTrue
, indicating that the number being formed must not exceedn
. 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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 is101
. - Reverse it to get
a = [1,0,1]
, and setl = 3
since there are three bits in the binary representation.
Step 2: Call the dfs
function initially with dfs(l, 0, True)
.
pos
starts atl = 3
, which represents the most significant bit (MSB).pre
is0
, since there is no bit before the MSB.limit
isTrue
, as we must remain within the bounds ofn
.
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]
iflimit
is True, else 1. Sincelimit
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) andi
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)
β thelimit
becomes False sincei
is not equal toup
. - For
i = 1
:dfs(2, 1, True)
β we still respect the upper limit sincei
equalsup
.
- For
- If
- Since
- 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)
callsdfs(2, 0, False)
anddfs(2, 1, True)
dfs(2, 0, False)
callsdfs(1, 0, False)
(valid path) anddfs(1, 1, False)
(valid path)dfs(1, 0, False)
callsdfs(0, 0, False)
anddfs(0, 1, False)
β each returns 1 since these are valid, totaling 2.dfs(1, 1, False)
callsdfs(0, 0, False)
only (sincedfs(0, 1, False)
would have consecutive 1s) β returns 1.
dfs(2, 1, True)
callsdfs(1, 0, False)
(valid path)dfs(1, 0, False)
again callsdfs(0, 0, False)
anddfs(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.
Which of the following is a min heap?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question?Β Ask the Monster AssistantΒ anything you don't understand.
Still not clear? Β SubmitΒ the part you don't understand to our editors. Or join ourΒ Discord and ask the community.