Skip to main content
Talentd

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K - Solution & Explanation

MediumMathGreedy11 min readAsked at: Google
Practice this problem

Problem Statement

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:

  • F1 = 1
  • F2 = 1
  • Fn = Fn-1 + Fn-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 <= 109

Approach Overview

Problem Overview: You are given an integer k. The goal is to represent k as the sum of Fibonacci numbers using the minimum possible count. Each Fibonacci number can be used multiple times, and you want the smallest number of terms whose total equals k.

Approach 1: Greedy with Fibonacci Generation (O(log k) time, O(log k) space)

This problem works well with a greedy strategy. First generate all Fibonacci numbers less than or equal to k. The key observation is that subtracting the largest Fibonacci number not exceeding the current value always leads to an optimal solution. After subtracting it, repeat the same step with the remaining value until it reaches zero. Because Fibonacci numbers grow exponentially, there are only about 45 values up to 10^9, so generation and iteration are both very small.

The algorithm works as follows: build a Fibonacci list using iteration, then repeatedly find the largest value ≤ k, subtract it, and increment a counter. This greedy choice works due to properties of Fibonacci numbers (related to Zeckendorf’s theorem), which guarantees that every integer has a unique representation as a sum of non‑consecutive Fibonacci numbers. Time complexity is O(log k) because the Fibonacci sequence length grows logarithmically with k. Space complexity is also O(log k) for storing the sequence. This approach mainly relies on concepts from greedy algorithms and math.

Approach 2: Dynamic Programming / Coin Change Style (O(F Ă— k) time, O(k) space)

You can also frame the problem as a variation of the coin change problem. Treat each Fibonacci number ≤ k as a coin denomination and compute the minimum number of coins needed to reach exactly k. First generate all Fibonacci numbers up to k. Then build a DP array where dp[i] stores the minimum numbers required to form sum i. For each Fibonacci value, iterate through the DP array and update states similar to unbounded knapsack.

This method guarantees correctness because it explores every combination of Fibonacci numbers. However, the state space grows with k, which makes it impractical for large values such as 10^9. Time complexity becomes O(F × k), where F is the number of Fibonacci numbers ≤ k (around 45). Space complexity is O(k). The approach demonstrates classic dynamic programming reasoning but is usually unnecessary given the greedy property.

Recommended for interviews: The greedy approach is the expected solution. Interviewers want to see that you generate Fibonacci numbers efficiently and repeatedly subtract the largest valid value. Mentioning the mathematical property that guarantees optimality strengthens the explanation. A DP formulation shows broader problem‑solving ability, but the greedy solution demonstrates deeper insight and achieves optimal O(log k) performance.

Approach 1: Greedy Approach with Fibonacci Generation

This approach uses a greedy strategy to select the largest possible Fibonacci number that is less than or equal to the target sum, k, repeatedly until the remainder is zero. This ensures that the sum converges towards k quickly.

In this solution, we first generate a list of Fibonacci numbers up to the largest one less than or equal to k. Then, starting from the largest Fibonacci number, we subtract it from k until k reaches zero, increasing our count each time. The number of subtractions required gives us the minimum count of Fibonacci numbers needed to sum up to k.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(log k) because the number of Fibonacci numbers is logarithmic relative to k.
Space Complexity: O(log k) for storing the Fibonacci sequence.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

This approach involves using dynamic programming to build a solution by storing previously calculated results in an array to calculate the fewest sum of Fibonacci numbers that make up a number.

This Java solution demonstrates a similar logic where Fibonacci numbers are first generated, then used to minimize the count by subtracting from k using the largest possible Fibonacci numbers iteratively.

Code

Java

Java

Complexity

Time Complexity: O(log k).
Space Complexity: O(log k).

Try this approach in the editor →

Approach 3: Greedy

We can greedily select the largest Fibonacci number that does not exceed k each time, then subtract this number from k and increment the answer by one. This process is repeated until k = 0.

Since we greedily select the largest Fibonacci number that does not exceed k each time, suppose this number is b, the previous number is a, and the next number is c. Subtracting b from k results in a value that is less than a, which means that after selecting b, we will not select a. This is because if we could select a, then we could have greedily selected the next Fibonacci number c instead of b earlier, which contradicts our assumption. Therefore, after selecting b, we can greedily reduce the Fibonacci number.

The time complexity is O(log k), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Fibonacci Generation

Time Complexity: O(log k) because the number of Fibonacci numbers is logarithmic relative to k.
Space Complexity: O(log k) for storing the Fibonacci sequence.

Dynamic Programming Approach

Time Complexity: O(log k).
Space Complexity: O(log k).

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Fibonacci GenerationO(log k)O(log k)Best approach for large k. Uses the largest Fibonacci ≤ remaining value each step.
Dynamic Programming (Coin Change)O(F Ă— k)O(k)Useful for understanding the problem as a coin change variant or when constraints on k are small.

Video Solution

Leetcode 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K • Fraz • 5,891 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Find the Minimum Number of Fibonacci Numbers Whose Sum Is K easy or hard?
The problem is classified as Medium on LeetCode. Implementation is straightforward once you recognize the greedy pattern, but the key challenge is realizing that choosing the largest Fibonacci number at each step always leads to the optimal minimum count.
Find the Minimum Number of Fibonacci Numbers Whose Sum Is K Python/Java solution
Python and C++ implementations typically follow the greedy strategy: generate Fibonacci numbers, then repeatedly subtract the largest valid value while counting steps. A Java implementation can also demonstrate a dynamic programming approach similar to coin change, though the greedy method is more efficient for large inputs.
How to solve Find the Minimum Number of Fibonacci Numbers Whose Sum Is K in O(log k)?
First generate all Fibonacci numbers less than or equal to k. Starting from the largest Fibonacci number, subtract it from k if it is not greater than the remaining value. Continue subtracting the largest possible Fibonacci number until k becomes zero. Each subtraction reduces the remaining value quickly, leading to O(log k) complexity.
What is the best approach for Find the Minimum Number of Fibonacci Numbers Whose Sum Is K?
The greedy approach is the most efficient solution. Generate Fibonacci numbers up to k, then repeatedly subtract the largest Fibonacci number less than or equal to the remaining value. This works due to properties of Fibonacci numbers that guarantee an optimal representation. The overall time complexity is O(log k).
Is Find the Minimum Number of Fibonacci Numbers Whose Sum Is K asked at Google/Amazon/Meta?
Greedy and Fibonacci-based problems similar to this appear in interviews at large tech companies such as Google, Amazon, and Meta. The question tests understanding of greedy strategy, mathematical sequences, and recognizing when a greedy choice is provably optimal.
What data structure is used in Find the Minimum Number of Fibonacci Numbers Whose Sum Is K?
The solution mainly uses an array or list to store generated Fibonacci numbers. The greedy process then iterates through this list from largest to smallest to subtract valid values. No complex data structures are required beyond simple iteration and arithmetic operations.
What is the time complexity of Find the Minimum Number of Fibonacci Numbers Whose Sum Is K?
The optimal greedy solution runs in O(log k) time because the Fibonacci sequence grows exponentially and contains only about 45 numbers up to 1e9. Each step subtracts the largest valid Fibonacci value, and the number of iterations remains small. Space complexity is O(log k) to store the Fibonacci numbers.

Ready to solve this problem?

Practice Find the Minimum Number of Fibonacci Numbers Whose Sum Is K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer