Package g1401_1500.s1414_find_the_minimum_number_of_fibonacci_numbers_whose_sum_is_k

Class Solution

java.lang.Object
g1401_1500.s1414_find_the_minimum_number_of_fibonacci_numbers_whose_sum_is_k.Solution
public class Solution extends Object
1414 - Find the Minimum Number of Fibonacci Numbers Whose Sum Is K.<p>Medium</p> <p>Given an integer <code>k</code>, <em>return the minimum number of Fibonacci numbers whose sum is equal to</em> <code>k</code>. The same Fibonacci number can be used multiple times.</p> <p>The Fibonacci numbers are defined as:</p> <ul> <li><code>F<sub>1</sub> = 1</code></li> <li><code>F<sub>2</sub> = 1</code></li> <li><code>F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub></code> for <code>n > 2.</code></li> </ul> <p>It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to <code>k</code>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> k = 7</p> <p><strong>Output:</strong> 2</p> <p><strong>Explanation:</strong> The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, &hellip; For k = 7 we can use 2 + 5 = 7.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> k = 10</p> <p><strong>Output:</strong> 2</p> <p><strong>Explanation:</strong> For k = 10 we can use 2 + 8 = 10.</p> <p><strong>Example 3:</strong></p> <p><strong>Input:</strong> k = 19</p> <p><strong>Output:</strong> 3</p> <p><strong>Explanation:</strong> For k = 19 we can use 1 + 5 + 13 = 19.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= k <= 10<sup>9</sup></code></li> </ul>

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • findMinFibonacciNumbers

      public int findMinFibonacciNumbers(int k)