Menu Close

Find the minimum number of Fibonacci numbers whose sum is equal to k

Given the number k, return the minimum number of Fibonacci numbers whose sum is equal to k, whether a Fibonacci number could be used multiple times. The Fibonacci numbers are defined as:
F1 = 1
F2 = 1
Fn=Fn-1 + Fn-2, for n > 2.
It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum k.
Input: k=7
Output: 2

def fibo(x):
    if x <= 1:
        return x
    else:
        return (fibo(x-1)+fibo(x-2))

N=int(input('Enter the K value : '))
L=[]
for i in range(N):
    if fibo(i) < N:
        L.append(fibo(i))
    else: break

i,c=0,0
L=sorted(L,reverse=True)
while i<len(L)-1:
    c+=N//L[i]
    N%=L[i]
    i+=1
print(c)

Input_1:
Enter the K value : 7
Output:
2

Input_2:
Enter the K value : 10
Output:
2

Input_3:
Enter the K value : 19
Output:
3

Input_4:
Enter the K value : 900
Output:
4

Input_5:
Enter the K value : 17
Output:
3

Morae Q!