1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K Medium

1/**
2 * [1414] Find the Minimum Number of Fibonacci Numbers Whose Sum Is K
3 *
4 * 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.
5 * The Fibonacci numbers are defined as:
6 * 
7 * 	F1 = 1
8 * 	F2 = 1
9 * 	Fn = Fn-1 + Fn-2 for n > 2.
10 * It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to k.
11 *  
12 * Example 1:
13 * 
14 * Input: k = 7
15 * Output: 2 
16 * Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... 
17 * For k = 7 we can use 2 + 5 = 7.
18 * Example 2:
19 * 
20 * Input: k = 10
21 * Output: 2 
22 * Explanation: For k = 10 we can use 2 + 8 = 10.
23 * 
24 * Example 3:
25 * 
26 * Input: k = 19
27 * Output: 3 
28 * Explanation: For k = 19 we can use 1 + 5 + 13 = 19.
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	1 <= k <= 10^9
34 * 
35 */
36pub struct Solution {}
37
38// problem: https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/
39// discuss: https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/discuss/?currentPage=1&orderBy=most_votes&query=
40
41// submission codes start here
42
43impl Solution {
44    pub fn find_min_fibonacci_numbers(k: i32) -> i32 {
45        0
46    }
47}
48
49// submission codes end
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test_1414() {
57    }
58}
59