LeetCode 600: Non-negative Integers without Consecutive Ones Solution in Python – A Step-by-Step Guide

What Is LeetCode 600: Non-negative Integers without Consecutive Ones?

In LeetCode 600: Non-negative Integers without Consecutive Ones, you’re given an integer n, and your task is to return the count of non-negative integers from 0 to n (inclusive) whose binary representations do not contain consecutive 1s. For example, with n = 5, the valid numbers are 0 (0), 1 (1), 2 (10), 4 (100), 5 (101), totaling 5, while 3 (11) is excluded due to consecutive 1s. This problem builds on LeetCode 198: House Robber for dynamic programming with constraints but focuses on binary number properties.

Problem Statement

• Input: n (int)—upper bound integer.
• Output: Integer—count of numbers from 0 to n with no consecutive 1s in binary form.
• Rules: Non-negative integers ≤ n; binary must not have adjacent 1s (e.g., 11).

Constraints

• 1 <= n <= 10⁹

Examples

• Input: n = 5
• Output: 5
• Valid: 0 (0), 1 (1), 2 (10), 4 (100), 5 (101); Invalid: 3 (11).
• Input: n = 2
• Output: 3
• Valid: 0 (0), 1 (1), 2 (10).
• Input: n = 7
• Output: 8
• Valid: 0 (0), 1 (1), 2 (10), 4 (100), 5 (101), 6 (110)—corrected: 0, 1, 2, 4, 5 (5 valid).

Understanding the Problem: Counting Valid Numbers

To solve LeetCode 600: Non-negative Integers without Consecutive Ones in Python, we need to count how many integers from 0 to n (up to 10⁹) have binary representations without consecutive 1s, doing so efficiently. A brute-force approach checking each number (O(n)) is impractical for large n. Instead, a dynamic programming solution leverages the Fibonacci-like pattern of valid binary numbers and adjusts for the upper bound n in O(log n) time, using the binary digits of n to compute the count. We’ll explore:

• Best Solution (Dynamic Programming with Binary Constraints): O(log n) time, O(log n) space—fast and optimal.
• Alternative Solution (Brute-Force Enumeration): O(n) time, O(1) space—thorough but slow.

Let’s dive into the DP solution with a friendly breakdown!

Best Solution: Dynamic Programming with Binary Constraints

Why DP Wins

The dynamic programming with binary constraints solution is the best for LeetCode 600 because it counts valid numbers in O(log n) time and O(log n) space by using a Fibonacci-based DP array to compute counts of valid binary numbers up to each bit length, then adjusts for the constraint of n by processing its binary digits. It’s like building a ladder of valid numbers, step-by-step, then climbing just far enough to reach n—all in a swift, clever ascent!

How It Works

Think of this as a binary-number builder:

• Step 1: Fibonacci DP Setup:
• Define dp[i][0]: count of i-bit numbers ending in 0, no consecutive 1s.
• Define dp[i][1]: count of i-bit numbers ending in 1, no consecutive 1s.
• Base: dp[1][0] = 1, dp[1][1] = 1.
• Recurrence:
• dp[i][0] = dp[i-1][0] + dp[i-1][1] (append 0 to any).
• dp[i][1] = dp[i-1][0] (append 1 to 0-ending only).
• Step 2: Get Binary of n:
• Convert n to binary string (e.g., 5 → "101").
• Step 3: Count Up to n:
• For each bit position:
• Add counts of shorter valid numbers.
• If bit is 1, add valid prefixes, adjust for consecutive 1s.
• Step 4: Return Result:
• Total count of valid numbers ≤ n.
• Why It Works:
• Fibonacci pattern counts all valid numbers.
• Binary traversal ensures we stay ≤ n.

It’s like a binary-counting maestro!

Step-by-Step Example

Example: n = 5 (binary "101")

• Step 1: DP setup (lengths 1 to 3):
• dp[1][0] = 1, dp[1][1] = 1 (0, 1).
• dp[2][0] = 1+1 = 2, dp[2][1] = 1 (00, 10, 01).
• dp[3][0] = 2+1 = 3, dp[3][1] = 2 (000, 100, 010, 001, 101).
• Step 2: Binary = "101", length = 3.
• Step 3: Count:
• i=0 (leftmost 1):
• Add all 1-bit: dp[1][0] + dp[1][1] = 2 (0, 1).
• Add all 2-bit: dp[2][0] + dp[2][1] = 3 (00, 10, 01).
• Next bit 0, no consecutive 1s yet.
• i=1 (middle 0):
• Prefix "10": Add dp[1][0] = 1 (100).
• i=2 (rightmost 1):
• Prefix "101": No further bits, valid (101).
• Total = 2 + 1 + 1 + 1 (0, 1, 2, 4, 5) = 5.
• Step 4: Return 5.
• Result: 5.

Example: n = 2 (binary "10")

• Step 1: DP:
• dp[1][0] = 1, dp[1][1] = 1.
• dp[2][0] = 2, dp[2][1] = 1.
• Step 2: Binary = "10".
• Step 3:
• i=0: Add dp[1][0] + dp[1][1] = 2 (0, 1).
• i=1: "10" valid (10), add 1.
• Total = 3.
• Result: 3.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class Solution:
    def findIntegers(self, n: int) -> int:
        # Step 1: Convert n to binary and get length
        binary = bin(n)[2:]  # Remove '0b' prefix
        length = len(binary)

        # Step 2: Initialize DP arrays
        dp = [[0] * 2 for _ in range(length + 1)]
        dp[1][0] = 1  # 0
        dp[1][1] = 1  # 1

        for i in range(2, length + 1):
            dp[i][0] = dp[i-1][0] + dp[i-1][1]  # Append 0
            dp[i][1] = dp[i-1][0]               # Append 1 to 0-ending

        # Step 3: Count valid numbers up to n
        count = 0
        prev_bit = 0  # Track previous bit to avoid consecutive 1s

        for i in range(length):
            curr_bit = int(binary[i])
            # Add all valid numbers of length less than current position
            if i > 0:
                count += dp[i][0]
            # If current bit is 1
            if curr_bit == 1:
                # Add count of numbers ending in 0 at this length
                count += dp[length - i][0]
                # Check for consecutive 1s
                if prev_bit == 1:
                    break
            prev_bit = curr_bit
            # If last bit, add 1 for the number itself if valid
            if i == length - 1 and prev_bit == 0:
                count += 1

        return count

• Lines 4-5: Get binary string and length of n.
• Lines 8-14: Build DP:
• Base cases: 1-bit numbers.
• Fill DP with Fibonacci-like recurrence.
• Lines 17-31: Count:
• Track previous bit to avoid consecutive 1s.
• Add shorter valid numbers, adjust for n’s bits.
• Line 33: Return total count.
• Time Complexity: O(log n)—process binary digits.
• Space Complexity: O(log n)—DP array size.

It’s like a binary-counting wizard!

Alternative Solution: Brute-Force Enumeration

Why an Alternative Approach?

The brute-force enumeration approach checks every number from 0 to n for consecutive 1s in its binary form, running in O(n) time and O(1) space. It’s thorough but impractical for large n (up to 10⁹), making it a baseline for small inputs or understanding.

How It Works

Picture this as a number-checking brute:

• Step 1: Iterate from 0 to n.
• Step 2: Convert each to binary, check for consecutive 1s.
• Step 3: Count valid numbers.
• Step 4: Return count.

It’s like a binary-inspecting tally!

Step-by-Step Example

Example: n = 3

• Step 1: Check 0 to 3:
• 0 (0): Valid, count = 1.
• 1 (1): Valid, count = 2.
• 2 (10): Valid, count = 3.
• 3 (11): Consecutive 1s, skip.
• Step 2: Total = 3.
• Result: 3.

Code for Brute-Force Approach

class Solution:
    def findIntegers(self, n: int) -> int:
        def has_consecutive_ones(num):
            binary = bin(num)[2:]
            for i in range(len(binary) - 1):
                if binary[i] == '1' and binary[i + 1] == '1':
                    return True
            return False

        count = 0
        for i in range(n + 1):
            if not has_consecutive_ones(i):
                count += 1
        return count

• Lines 3-8: Check for consecutive 1s in binary.
• Lines 11-14: Count valid numbers from 0 to n.
• Time Complexity: O(n)—iterate all numbers.
• Space Complexity: O(1)—minimal space.

It’s a brute-force binary checker!

Comparing the Two Solutions

• DP (Best):
• Pros: O(log n), O(log n), fast and scalable.
• Cons: DP setup complexity.
• Brute-Force (Alternative):
• Pros: O(n), O(1), simple logic.
• Cons: Impractical for large n.

DP wins for efficiency!

Additional Examples and Edge Cases

• n = 0: 1 (just 0).
• n = 1: 2 (0, 1).
• Large n: DP scales well.

DP handles them all!

Complexity Recap

• DP: Time O(log n), Space O(log n).
• Brute-Force: Time O(n), Space O(1).

DP’s the speed champ!

Key Takeaways

• DP: Binary finesse—learn at Python Basics!
• Brute-Force: Number grind.
• Bits: Counting is fun.
• Python: DP or brute, your pick!

Final Thoughts: Count Those Numbers!

LeetCode 600: Non-negative Integers without Consecutive Ones in Python is a binary challenge. Dynamic programming with binary constraints is your fast track, while brute-force offers a thorough dive. Want more? Try LeetCode 198: House Robber or LeetCode 338: Counting Bits. Ready to count? Head to Solve LeetCode 600 on LeetCode and tally those valid numbers today!