mediumGreedyMath 0 views
Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k.
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:
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 <= 10^9
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.