Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Med

#1308Time: O(k * log k) - The outer loop runs `k` times, and the inner loop iterates through the Fibonacci numbers, of which there are `O(log k)` up to `k`. This is too slow for `k = 10^9`.Space: O(k) - We need an array of size `k+1` to store the DP states. For `k = 10^9`, this is not feasible.

Patterns

Math Greedy

Prompt

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:

F₁ = 1
F₂ = 1
F_n = F_n-1 + F_n-2 for n > 2.

It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to k.

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⁹

Approaches

2 approaches with complexity analysis and trade-offs.

A standard approach for problems that ask for the minimum number of items to form a specific sum is dynamic programming. We can define dp[i] as the minimum number of Fibonacci numbers that sum to i. By building up the solution for k from smaller subproblems, we can find the answer. However, this approach is too slow and memory-intensive for the given constraints on k.

Algorithm

First, generate all Fibonacci numbers f such that f <= k.
Create a DP array, dp, of size k + 1. dp[i] will store the minimum number of Fibonacci numbers needed to form the sum i.
Initialize dp[0] = 0 and all other dp[i] to a large value (infinity).
Iterate from i = 1 to k. For each i, iterate through the generated Fibonacci numbers f.
The recurrence relation is dp[i] = min(dp[i], 1 + dp[i - f]) for every Fibonacci number f <= i.
The final answer is dp[k].

Walkthrough

This method involves building a table of solutions for all values from 1 to k. We define dp[i] as the minimum count of Fibonacci numbers that sum up to i.

The process is as follows:

Generate all unique Fibonacci numbers less than or equal to k.
Create a dp array of size k + 1 and initialize all its values to infinity, except for dp[0], which is 0 (since 0 requires zero Fibonacci numbers).
We then fill the dp table iteratively. For each number i from 1 to k, we try to form it by adding a Fibonacci number f to a previously computed sum i - f. The number of Fibonacci numbers for i would be 1 + dp[i - f]. We do this for all possible Fibonacci numbers f <= i and take the one that results in the minimum count.
The final result is stored in dp[k].

While correct, the large value of k makes this approach impractical.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4 5class Solution {6    public int findMinFibonacciNumbers(int k) {7        // This approach is too slow and memory-intensive for the given constraints.8        // It is provided for illustrative purposes.9 10        // Generate unique Fibonacci numbers up to k11        List<Integer> fibs = new ArrayList<>();12        int a = 1, b = 1;13        fibs.add(1);14        while (b <= k) {15            int temp = a + b;16            a = b;17            b = temp;18            if (b <= k) {19                fibs.add(b);20            }21        }22 23        int[] dp = new int[k + 1];24        Arrays.fill(dp, k + 1); // Initialize with a value larger than any possible answer25        dp[0] = 0;26 27        for (int i = 1; i <= k; i++) {28            for (int fib : fibs) {29                if (i >= fib) {30                    dp[i] = Math.min(dp[i], 1 + dp[i - fib]);31                } else {32                    break; // Optimization as fibs is sorted33                }34            }35        }36        return dp[k];37    }38}

Complexity

Time

O(k * log k) - The outer loop runs `k` times, and the inner loop iterates through the Fibonacci numbers, of which there are `O(log k)` up to `k`. This is too slow for `k = 10^9`.

Space

O(k) - We need an array of size `k+1` to store the DP states. For `k = 10^9`, this is not feasible.

Trade-offs

Pros

It's a standard and straightforward application of dynamic programming.
Guaranteed to find the optimal solution for any similar change-making problem.

Cons

Highly inefficient for large k.
The time complexity of O(k * log k) is too slow for the given constraints, leading to a Time Limit Exceeded (TLE) error.
The space complexity of O(k) requires a very large amount of memory for k up to 10^9, leading to a Memory Limit Exceeded (MLE) error.

A much more efficient solution is a greedy algorithm. The core idea is to always subtract the largest possible Fibonacci number from the remaining value of k. This works because of a special property of Fibonacci numbers which guarantees that this greedy choice is always part of an optimal solution. This method is extremely fast and uses minimal memory, making it ideal for the given constraints.

Algorithm

Generate Fibonacci numbers F_1, F_2, ... and store them in a list fibs until the generated number is greater than k.
Initialize a counter count = 0.
Start from the largest number in fibs and move downwards (e.g., using an index i from fibs.size() - 1 to 0).
While k > 0:
- If the current Fibonacci number fibs.get(i) is less than or equal to k:
  - Subtract it from k: k = k - fibs.get(i).
  - Increment the counter: count = count + 1.
- Move to the next smaller Fibonacci number: i = i - 1.
Return count.

Walkthrough

The greedy strategy is based on the insight that to minimize the number of terms in a sum, one should use the largest possible numbers first. For Fibonacci numbers, this strategy is proven to be optimal.

The algorithm proceeds as follows:

First, we generate all Fibonacci numbers that are less than or equal to k. Since Fibonacci numbers grow exponentially, this list will be small (fewer than 50 numbers for k up to 10^9).
We initialize a counter to 0.
We iterate from the largest generated Fibonacci number downwards. At each step, we check if the current Fibonacci number f can be subtracted from the remaining k (i.e., f <= k).
If it can, we perform the subtraction (k = k - f) and increment our counter. This greedy choice is optimal because any sum of smaller Fibonacci numbers that could replace f would require more terms.
We repeat this until k becomes 0. The final count is our answer.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int findMinFibonacciNumbers(int k) {6        // Step 1: Generate Fibonacci numbers up to k.7        List<Integer> fibs = new ArrayList<>();8        fibs.add(1);9        fibs.add(1);10        while (fibs.get(fibs.size() - 1) < k) {11            int n = fibs.size();12            fibs.add(fibs.get(n - 1) + fibs.get(n - 2));13        }14 15        // Step 2: Use a greedy approach to find the minimum number of terms.16        int count = 0;17        int i = fibs.size() - 1;18        while (k > 0) {19            if (fibs.get(i) <= k) {20                k -= fibs.get(i);21                count++;22            }23            i--;24        }25        return count;26    }27}

Complexity

Time

O(log k) - Generating the Fibonacci numbers takes `O(log k)` time. The greedy subtraction loop also takes `O(log k)` time as it iterates through the list of Fibonacci numbers once.

Space

O(log k) - We need to store the list of Fibonacci numbers up to `k`. The number of such Fibonacci numbers is proportional to `log(k)`.

Trade-offs

Pros

Extremely efficient, with logarithmic time and space complexity.
Simple to implement once the greedy strategy is known.
Easily handles the large constraints on k.

Cons

The correctness of the greedy approach is not immediately obvious and relies on a specific mathematical property of Fibonacci numbers (related to Zeckendorf's theorem).

Solutions

Solution

1class Solution {2public3  int findMinFibonacciNumbers(int k) {4    if (k < 2) {5      return k;6    }7    int a = 1, b = 1;8    while (b <= k) {9      b = a + b;10      a = b - a;11    }12    return 1 + findMinFibonacciNumbers(k - a);13  }14}

1class Solution {2public:3  int findMinFibonacciNumbers(int k) {4    if (k < 2)5      return k;6    int a = 1, b = 1;7    while (b <= k) {8      b = a + b;9      a = b - a;10    }11    return 1 + findMinFibonacciNumbers(k - a);12  }13};

1class Solution:2    def findMinFibonacciNumbers(self, k: int) -> int: def dfs(k): if k < 2: return k a = b = 1 while b <= k: a, b = b, a + b return 1 + dfs(k - a) return dfs(k)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem