Find the Minimum Number of Fibonacci Numbers Whose Sum Is K - Practice Coding | SlaveCode
0
0123456789
0
0123456789
:
0
0123456789
0
0123456789
1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
Medium
30 Points
Math
Greedy
Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k. The same Fibonacci number can be used multiple times.
The Fibonacci numbers are defined as:
Examples
Example 1
Input: k = 7
Output: 2
Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ...
For k = 7 we can use 2 + 5 = 7.
Example 2
Input: k = 10
Output: 2
Explanation: For k = 10 we can use 2 + 8 = 10.
Example 3
Input: k = 19
Output: 3
Explanation: For k = 19 we can use 1 + 5 + 13 = 19.
Constraints
1 <= k <= 109
1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
Medium
30 Points
Math
Greedy
Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k. The same Fibonacci number can be used multiple times.
The Fibonacci numbers are defined as:
Examples
Example 1
Input: k = 7
Output: 2
Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ...
For k = 7 we can use 2 + 5 = 7.
Example 2
Input: k = 10
Output: 2
Explanation: For k = 10 we can use 2 + 8 = 10.
Example 3
Input: k = 19
Output: 3
Explanation: For k = 19 we can use 1 + 5 + 13 = 19.