# LeetCode 600: Non-negative Integers without Consecutive Ones ## Problem Restatement We are given a positive integer `n`. We need to count how many integers in the range `[0, n]` have binary representations that do not contain consecutive `1` bits. For example, `3` has binary representation: ```text 11 ``` so it is invalid. But `5` has binary representation: ```text 101 ``` so it is valid. Return the count of valid integers from `0` through `n`, inclusive. The official problem asks for integers in `[0, n]` whose binary representations do not contain consecutive ones. ## Input and Output | Item | Meaning | |---|---| | `n` | Upper bound of the range | | Output | Count of integers `x` where `0 <= x <= n` and binary `x` has no `"11"` | Example function shape: ```python def findIntegers(n: int) -> int: ... ``` ## Examples Example 1: ```python n = 5 ``` Output: ```python 5 ``` The integers from `0` to `5` are: | Number | Binary | Valid | |---:|---|---| | `0` | `0` | yes | | `1` | `1` | yes | | `2` | `10` | yes | | `3` | `11` | no | | `4` | `100` | yes | | `5` | `101` | yes | So the answer is `5`. Example 2: ```python n = 1 ``` Output: ```python 2 ``` Both `0` and `1` are valid. Example 3: ```python n = 2 ``` Output: ```python 3 ``` The valid numbers are `0`, `1`, and `2`. Their binary forms are: ```text 0 1 10 ``` ## First Thought: Check Every Number A direct solution is to loop over every number from `0` to `n`. For each number: 1. Convert it to binary. 2. Check whether the string contains `"11"`. 3. Count it if it does not. ```python class Solution: def findIntegers(self, n: int) -> int: answer = 0 for x in range(n + 1): if "11" not in bin(x): answer += 1 return answer ``` This is simple, but it is too slow when `n` is large. We need to count valid binary strings without enumerating every integer. ## Key Insight The problem is about binary digits, not decimal values. We can count valid binary strings by length. Let: ```text dp[length] ``` be the number of binary strings of length `length` that do not contain consecutive ones. For length `1`, the valid strings are: ```text 0 1 ``` For length `2`, the valid strings are: ```text 00 01 10 ``` The recurrence is Fibonacci-like: ```text dp[i] = dp[i - 1] + dp[i - 2] ``` Why? A valid string of length `i` either: 1. Starts with `0`, followed by any valid string of length `i - 1`. 2. Starts with `10`, followed by any valid string of length `i - 2`. It cannot start with `11`. So we can precompute how many valid suffixes exist for each remaining length. Then we scan the bits of `n` from most significant to least significant. Whenever we see a `1`, we can count all valid numbers that put `0` at this bit and then freely fill the remaining lower bits. ## Binary Counting Idea Suppose: ```python n = 5 ``` Binary: ```text 101 ``` Scan from left to right. At the first bit, `n` has `1`. Numbers less than `n` can put `0` here: ```text 0?? ``` The remaining two bits can be any valid binary string of length `2`. There are `3` such strings: ```text 00 01 10 ``` So we add `3`. Then we follow the original bit `1`. At the next bit, `n` has `0`, so we cannot choose a smaller bit there. Continue. At the final bit, `n` has `1`. Numbers can put `0` there: ```text 100 ``` So we add `1`. Finally, `n = 101` itself is valid, so we add `1`. Total: ```text 3 + 1 + 1 = 5 ``` ## Algorithm 1. Convert `n` to a binary string. 2. Precompute `dp`, where `dp[i]` is the number of valid binary strings of length `i`. 3. Scan the binary string from left to right. 4. Track the previous bit. 5. When the current bit is `1`: - Add `dp[remaining_length]`, because we can place `0` here and freely fill the rest. 6. If we ever see two consecutive `1`s: - Stop and return the count so far. - We do not add `n` itself because `n` is invalid. 7. If the scan finishes without consecutive ones: - Add `1` for `n` itself. 8. Return the count. ## Correctness The DP array counts valid binary suffixes by length. For any length `i`, every valid string either begins with `0` followed by a valid string of length `i - 1`, or begins with `10` followed by a valid string of length `i - 2`. These two cases are disjoint and complete, so the recurrence counts exactly all valid strings of that length. During the scan of `n`, when the current bit is `1`, choosing `0` at that position creates a number strictly smaller than `n` while keeping all earlier bits equal. The remaining lower bits may be any valid binary suffix of the remaining length, and `dp[remaining_length]` counts exactly those choices. If two consecutive `1`s appear in the prefix of `n`, then `n` itself and any number with the same prefix up to that point are invalid. All valid numbers smaller than `n` that differ earlier have already been counted, so returning immediately is correct. If the scan completes without consecutive `1`s, then `n` itself is valid. The algorithm adds `1` for `n`. Therefore, the algorithm counts exactly the integers in `[0, n]` whose binary representations do not contain consecutive ones. ## Complexity Let: ```text L = number of bits in n ``` | Metric | Value | Why | |---|---:|---| | Time | `O(L)` | We precompute `dp` and scan the binary digits once | | Space | `O(L)` | The DP array stores one value per bit length | Since `L = O(log n)`, the algorithm runs in `O(log n)` time. ## Implementation ```python class Solution: def findIntegers(self, n: int) -> int: bits = bin(n)[2:] length = len(bits) dp = [0] * (length + 1) dp[0] = 1 dp[1] = 2 for i in range(2, length + 1): dp[i] = dp[i - 1] + dp[i - 2] answer = 0 prev_bit = "0" for i, bit in enumerate(bits): remaining = length - i - 1 if bit == "1": answer += dp[remaining] if prev_bit == "1": return answer prev_bit = bit return answer + 1 ``` ## Code Explanation We first get the binary representation: ```python bits = bin(n)[2:] ``` For example: ```python n = 5 bits = "101" ``` The DP table stores the number of valid binary strings for each length: ```python dp[0] = 1 dp[1] = 2 ``` There is one valid string of length `0`: the empty suffix. There are two valid strings of length `1`: `0` and `1`. Then: ```python dp[i] = dp[i - 1] + dp[i - 2] ``` counts valid strings of length `i`. The scan starts with: ```python answer = 0 prev_bit = "0" ``` For each `1` bit: ```python answer += dp[remaining] ``` This counts all valid numbers that are smaller than `n` by putting `0` at this bit. If we see consecutive ones: ```python if prev_bit == "1": return answer ``` we stop because `n` itself is invalid. If the loop finishes, `n` has no consecutive ones, so we add `1`: ```python return answer + 1 ``` ## Digit DP Alternative We can also solve this with memoized digit DP. The state is: ```text position, previous_bit, tight ``` where `tight` means the current prefix is still equal to the prefix of `n`. ```python from functools import cache class Solution: def findIntegers(self, n: int) -> int: bits = bin(n)[2:] @cache def dfs(i: int, prev: int, tight: bool) -> int: if i == len(bits): return 1 limit = int(bits[i]) if tight else 1 total = 0 for bit in range(limit + 1): if prev == 1 and bit == 1: continue total += dfs( i + 1, bit, tight and bit == limit, ) return total return dfs(0, 0, True) ``` This version is easier to generalize to other digit DP problems. ## Testing ```python def run_tests(): s = Solution() assert s.findIntegers(0) == 1 assert s.findIntegers(1) == 2 assert s.findIntegers(2) == 3 assert s.findIntegers(3) == 3 assert s.findIntegers(4) == 4 assert s.findIntegers(5) == 5 assert s.findIntegers(6) == 5 assert s.findIntegers(7) == 5 assert s.findIntegers(8) == 6 assert s.findIntegers(9) == 7 print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | `0` | Only `0` is valid | | `1` | `0`, `1` | | `2` | `0`, `1`, `10` | | `3` | `11` is invalid | | `5` | Main sample | | `6` | `110` is invalid and does not add itself | | `7` | Consecutive ones early | | `8`, `9` | Counts across a new bit length |