#600

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Non-negative Integers without Consecutive Ones

Count non-negative integers up to n without consecutive ones in their binary representation using dynamic programming.

Problem Statement

Given a positive integer n, return the number of non-negative integers less than or equal to n whose binary representations do not contain consecutive ones. For example, when n = 5, there are 5 integers (0, 1, 2, 4, 5) that satisfy the condition, while 3 (which has two consecutive ones) is excluded.

This problem can be approached using dynamic programming with state transitions. The challenge lies in efficiently counting numbers without consecutive ones while staying within the given constraint of n being as large as 10^9.

Examples

Example 1

Input: n = 5

Output: 5

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 details omitted.

Example 3

Input: n = 2

Output: 3

Example details omitted.

Constraints

1 <= n <= 109

Solution Approach

Dynamic Programming with State Transition

We can break the problem down into counting valid numbers bit by bit. Use a dynamic programming approach to store the count of valid numbers up to each bit position. The transition depends on whether the previous bit was set to 1 or 0. If the previous bit was 1, the current bit must be 0 to avoid consecutive ones.

Fibonacci-like Sequence

The number of valid numbers up to a given bit length follows a Fibonacci-like pattern. If you think of the problem in terms of sequences, the valid numbers with k bits can be derived from valid numbers with k-1 and k-2 bits. This insight helps optimize the solution to linear time complexity.

Optimized Approach for Large n

For large n (up to 10^9), we focus on the binary representation of n and use dynamic programming to track the valid numbers up to each bit position. The solution takes advantage of bit manipulation and the Fibonacci-like property of the problem to avoid iterating over all numbers up to n.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of bits in n. Since n can be as large as 10^9, its binary representation will have at most 30 bits. Hence, the solution works in O(log n) time, where log n is the number of bits in n. The space complexity is also O(log n) due to the storage required for the dynamic programming table.

What Interviewers Usually Probe

Tests the candidate's understanding of dynamic programming and state transitions.
Evaluates the candidate’s ability to handle large inputs efficiently with bit manipulation.
Assesses the ability to recognize patterns in the problem, such as the Fibonacci-like sequence in counting valid numbers.

Common Pitfalls or Variants

Common pitfalls

Confusing consecutive ones with other binary patterns, leading to incorrect counting.
Inefficient brute force approaches that iterate through all numbers up to n instead of using dynamic programming.
Overlooking the importance of bit manipulation and Fibonacci-like properties in optimizing the solution for large values of n.

Follow-up variants

Modify the problem to count numbers with consecutive ones allowed but limited to a certain number of times.
Adapt the problem to count numbers with even or odd numbers of bits without consecutive ones.
Extend the problem to include additional constraints on the binary representations, such as limiting the total number of 1's.

FAQ

What is the main pattern to solve the Non-negative Integers without Consecutive Ones problem?

The main pattern involves dynamic programming with state transitions, specifically utilizing a Fibonacci-like sequence to count valid binary numbers.

How do I optimize the solution for large values of n?

To optimize for large n, use bit manipulation and dynamic programming to track valid numbers bit by bit, reducing the problem to O(log n) time complexity.

What is the time complexity of solving this problem?

The time complexity is O(log n), where n is the input number, as the solution processes the binary representation of n.

Can I solve this problem using brute force?

While brute force can work for small inputs, it is inefficient for large values of n. A dynamic programming approach is necessary for optimal performance.

What is the relationship between Fibonacci numbers and this problem?

The number of valid numbers follows a Fibonacci-like sequence, where the count of valid numbers for k bits is derived from the counts for k-1 and k-2 bits.

terminal

Solution

Solution 1: Digit DP

This problem essentially asks for the number of numbers in the given range $[l, ..r]$ whose binary representation does not contain consecutive $1$s. The count is related to the number of digits and the value of each binary digit. We can use the concept of Digit DP to solve this problem. In Digit DP, the size of the number has little impact on the complexity.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def findIntegers(self, n: int) -> int:
        @cache
        def dfs(i: int, pre: int, limit: bool) -> int:
            if i < 0:
                return 1
            up = (n >> i & 1) if limit else 1
            ans = 0
            for j in range(up + 1):
                if pre and j:
                    continue
                ans += dfs(i - 1, j, limit and j == up)
            return ans

        return dfs(n.bit_length() - 1, 0, True)

Continue Practicing

#583 delete operation for two strings #576 out of boundary paths #629 k inverse pairs array