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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Non-negative Integers without Consecutive Ones

Number: 600

Difficulty: Hard

Paid? No

Companies: Pocket Gems

Problem Description

Given a positive integer n, the task is to count how many integers in the range [0, n] have binary representations that do not contain consecutive ones.

Key Insights

  • The valid integers can be constructed in a way similar to Fibonacci patterns because if you avoid consecutive ones, the decision for one bit depends on the previous bit.
  • Precompute a DP array where dp[i] represents the number of valid binary strings of length i.
  • Process the binary representation of n from the most significant bit and cumulatively count those numbers whose remaining bits can be filled without violating the consecutive ones rule.
  • Use a digit-DP-like greedy technique: if a bit is 1, count all valid numbers that could be placed in the remaining positions and ensure no consecutive ones appear.

Space and Time Complexity

Time Complexity: O(L), where L is the number of bits in n (approximately 31 for n up to 10^9).
Space Complexity: O(L) for storing the DP array and binary representation.

Solution

We begin by representing the integer n in binary and calculating its length. We precompute a dp array where dp[i] represents the count of valid binary sequences of length i that do not contain consecutive ones. The recurrence relation is based on the observation that for a valid string:

  • If a bit is 0, you can safely choose the next bit.
  • If a bit is 1, the next bit must be 0. This gives dp[i] = dp[i-1] + dp[i-2] (with proper base cases).

Next, we scan the binary representation of n from the most significant bit to the least significant bit. When a 1 is encountered, we add dp[remaining_bits] because this corresponds to all numbers with a 0 in that position and any valid filling for the rest. If we find two consecutive 1s during the scan, we stop the process since it indicates that numbers beyond this point would violate the rules. Finally, if the traversal completes without any violation, we include n itself as one valid number.

By leveraging precomputed values to account for valid completions of the binary number, we avoid brute forcing through every possibility, resulting in an efficient digit-style DP solution.

Code Solutions

# Python solution with line-by-line comments

def findIntegers(n: int) -> int:
    # Convert the integer n to its binary representation in a list of bits.
    bits = []
    temp = n
    while temp:
        bits.append(temp & 1)  # Append the least significant bit.
        temp //= 2            # Move to the next bit.
    bits.reverse()  # Reverse to get the binary representation from most to least significant bit.

    L = len(bits)  # Total number of bits.
    # DP array where dp[i] will store the count of valid binary strings of length i.
    dp = [0] * (L + 1)
    dp[0] = 1  # Base case: empty string.
    dp[1] = 2  # With one bit, valid strings are "0" and "1".

    # Precompute dp values using the recurrence relation.
    for i in range(2, L + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    ans = 0  # Initialize answer.
    prev_bit = 0  # To track the previous bit in the binary representation.

    # Process each bit in the binary representation.
    for i in range(L):
        if bits[i] == 1:
            # If current bit is 1, add all valid numbers for the remaining bits.
            ans += dp[L - i - 1]
            if prev_bit == 1:
                # If previous bit was also 1, break as further numbers will violate the rule.
                return ans
            prev_bit = 1
        else:
            prev_bit = 0

    # If we reached here without consecutive ones, include n itself.
    return ans + 1

# Example usage:
# print(findIntegers(5))  # Expected output: 5
← Back to All Questions