Count Binary Strings Without Consecutive Ones

Problem

Return the number of binary strings of length n that contain no two consecutive 1s.

Build the strings ending in 0 and ending in 1 as Fibonacci-style counts: a string ending in 1 must be preceded by 0, while a string ending in 0 extends anything. Assume n >= 1.

Hint

The counts follow the Fibonacci sequence shifted by two positions.

Test cases

case 1

in: [1]

expected: 2

case 2

in: [2]

expected: 3

case 3

in: [3]

expected: 5

case 4

in: [5]

expected: 13

case 5

in: [10]

expected: 144

Starter codePython

def count_binary_strings_no_ones(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor