We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Non-negative Integers without Consecutive Ones

Difficulty: Hard

Problem Description

Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.

Key Insights

  • The problem can be solved using dynamic programming to track valid binary representations.
  • A valid binary number is one that does not have consecutive '1's in its binary representation.
  • We can use Fibonacci-like sequences to count valid combinations of bits.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

The solution involves using dynamic programming to compute the number of valid binary representations up to a given number. We use a Fibonacci-like approach where:

  • dp[i] represents the count of valid integers with i bits.
  • The recurrence relation is based on whether the first bit is '0' or '1':
    • If the first bit is '0', the remaining bits can be anything valid for i-1 bits.
    • If the first bit is '1', the next bit must be '0', and the remaining bits can be anything valid for i-2 bits.

We also need to compare the binary representation of n with the valid configurations as we build our count.

Code Solutions

def findIntegers(n: int) -> int:
    # Create an array to store the counts of valid integers
    dp = [0] * 32
    dp[0], dp[1] = 1, 2  # Base cases

    # Fill the dp array with counts
    for i in range(2, 32):
        dp[i] = dp[i - 1] + dp[i - 2]

    prev_bit = 0
    count = 0
    for i in range(31, -1, -1):
        # Check if the ith bit is set in n
        if n & (1 << i):
            count += dp[i]  # If current bit is '1', add count of valid numbers with i bits
            if prev_bit == 1:  # If previous bit was also '1', we have consecutive ones
                return count  # Return as we exceed the limit
            prev_bit = 1  # Update previous bit to '1'
        else:
            prev_bit = 0  # Update previous bit to '0'

    return count + 1  # Include 'n' itself as it's valid
← Back to All Questions