Fibonacci Code Length

Problem

Use the Fibonacci sequence F1 = 1, F2 = 2, Fk = Fk-1 + Fk-2 and the Zeckendorf representation of n as a sum of non-consecutive Fibonacci numbers. If i is the largest index used, the Fibonacci codeword has i bits plus one terminating bit, so its length is i + 1. Return 0 for n <= 0.

Hint

Greedily subtract the largest Fibonacci number that fits; the largest index sets the length.

Test cases

case 1

in: [1]

expected: 2

case 2

in: [2]

expected: 3

case 3

in: [4]

expected: 4

case 4

in: [11]

expected: 6

case 5

in: [12]

expected: 6

Starter codePython

def fibonacci_code_length(n):
    # Your code here
    pass

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