Non-negative Integers without Consecutive Ones

Tested Python solution for LeetCode 600 with 30 pytest cases. Generate a practice environment with lcpy.

LeetCode 600, Hard. Topics: Dynamic Programming. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 30 parametrized pytest cases, and a playground notebook:

lcpy gen -n 600   # by problem number
lcpy gen -s non_negative_integers_without_consecutive_ones   # by problem name

​

Problem

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

​

Examples

Input: n = 5
Output: 5
Explanation:
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.

Input: n = 1
Output: 2

Input: n = 2
Output: 3

​

Constraints

• 1 <= n <= 10^9

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(log n)
    # Space: O(log n)
    def find_integers(self, n: int) -> int:
        bits = bin(n)[2:]
        fib = [1, 2]
        while len(fib) < len(bits):
            fib.append(fib[-1] + fib[-2])

        count = 0
        prev_bit = 0
        for i, bit_char in enumerate(bits):
            if bit_char == "1":
                count += fib[len(bits) - i - 1]
                if prev_bit == 1:
                    count -= 1
                    break
                prev_bit = 1
            else:
                prev_bit = 0
        return count + 1

​

Complexity

Time	Space
O(log n)	O(log n)

​

Tags