Find Minimum Fibonacci Numbers Whose Sum Is K: Greedy Decomposition

Given a positive integer k, find the minimum number of Fibonacci numbers whose sum equals k. You can use any Fibonacci number more than once. The Fibonacci sequence here starts with 1, 1, 2, 3, 5, 8, 13, 21, and so on.

This is LeetCode 1414: Find the Minimum Number of Fibonacci Numbers Whose Sum Is K, a medium problem that looks like it might need dynamic programming but actually yields to a clean greedy solution. The key is a mathematical property of Fibonacci numbers that guarantees greedy always works.

Why this problem matters

This problem is a great example of when greedy beats DP. Many sum-decomposition problems (like Coin Change) require dynamic programming because greedy fails for arbitrary denominations. But Fibonacci numbers have a special structure that makes greedy optimal. Recognizing when greedy works and when it does not is a core interview skill.

The problem also reinforces two fundamental techniques: generating a sequence up to a bound, and iterating through candidates from largest to smallest. Both show up constantly in number theory and math-flavored problems.

The key insight

The greedy approach works because of a result known as Zeckendorf's representation theorem. Every positive integer can be represented as a sum of non-consecutive Fibonacci numbers, and this representation is unique. Because of this structure, greedily picking the largest Fibonacci number that does not exceed the remaining value always produces the minimum count.

Think about it this way: if you skip a large Fibonacci number and use smaller ones instead, you need at least two smaller Fibonacci numbers to cover the same range. The Fibonacci growth rate means that every number in the sequence is less than the sum of all smaller numbers plus one. So using the largest one available is always at least as good as any combination of smaller ones.

The solution

def findMinFibonacciNumbers(k):
    fibs = [1, 1]
    while fibs[-1] < k:
        fibs.append(fibs[-1] + fibs[-2])

    count = 0
    for f in reversed(fibs):
        if f <= k:
            k -= f
            count += 1
        if k == 0:
            break
    return count

The solution has two phases. First, generate all Fibonacci numbers up to k. Start with [1, 1] and keep appending the sum of the last two until you reach or exceed k. This gives you the full set of Fibonacci "denominations" you can work with.

Second, iterate through those Fibonacci numbers from largest to smallest. At each step, if the current Fibonacci number fits into the remaining value of k, subtract it and increment the count. Once k reaches 0, you are done.

Visual walkthrough

Complexity analysis

Fibonacci numbers grow exponentially (roughly by a factor of 1.618 per step), so there are only about O(log k) Fibonacci numbers up to k. Generating them takes O(log k) time, and the greedy scan through them is also O(log k). The list of Fibonacci numbers uses O(log k) space. For the constraint k <= 10^9, that is roughly 44 Fibonacci numbers at most.

The building blocks

1. Generating Fibonacci numbers up to a limit

The first building block is constructing the Fibonacci sequence up to a target value. This is a standard pattern: start with the base cases and extend until you hit the bound.

fibs = [1, 1]
while fibs[-1] < k:
    fibs.append(fibs[-1] + fibs[-2])

You will see this same pattern in problems like Fibonacci Number and anywhere you need the Fibonacci sequence as a lookup table rather than a single value. The key detail is the stopping condition: you keep going until the last element reaches or exceeds k, so you know you have every Fibonacci number you might need.

2. Greedy subtraction from largest to smallest

The second building block is the greedy loop that subtracts the largest available value at each step.

count = 0
for f in reversed(fibs):
    if f <= k:
        k -= f
        count += 1
    if k == 0:
        break

This pattern appears whenever you have a set of values sorted in decreasing order and want to greedily decompose a target. The critical question is always whether greedy produces the optimal result. For arbitrary coin denominations it does not (that is why coin change needs DP). For Fibonacci numbers it does, thanks to their mathematical properties.

Edge cases

Before submitting, make sure your solution handles these:

• k = 1: the answer is 1. The smallest Fibonacci number is 1.
• k is itself a Fibonacci number: for example, k = 13. The greedy picks 13 immediately and the answer is 1.
• k requires many numbers: for example, k = 4 = 3 + 1. The greedy picks 3, then 1, for a count of 2.
• Large k: k = 10^9. There are only about 44 Fibonacci numbers up to 10^9, so the algorithm is fast.
• k = 2: the greedy picks 2 directly (since 2 is a Fibonacci number). Answer is 1.

From understanding to recall

You have seen the solution: generate Fibonacci numbers, then greedily subtract the largest. It is short and elegant. But can you reproduce it under pressure?

The details matter: remembering to generate the sequence first (not hardcode it), iterating in reverse order, and knowing why greedy works here but not for coin change. These distinctions are easy to mix up if you have not practiced writing them from scratch.

Spaced repetition closes that gap. You write the greedy Fibonacci decomposition from memory at increasing intervals. After a few rounds, the pattern is second nature. You see "minimum Fibonacci sum" and the code flows without hesitation.

The greedy subtraction pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Climbing Stairs - The classic Fibonacci-based DP problem, building intuition for Fibonacci properties
• Fibonacci Number - Generating the Fibonacci sequence, the same first building block used here
• Coin Change - A sum-decomposition problem where greedy fails and DP is required, a great contrast to this problem

CodeBricks breaks the Fibonacci sum problem into its sequence generation and greedy subtraction building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy decomposition question shows up in your interview, you do not think about it. You just write it.