Problem Description

You are given an integer k. Your task is to find the minimum number of Fibonacci numbers that sum up to exactly k. You can use the same Fibonacci number multiple times.

The Fibonacci sequence is defined as:

• F₁ = 1 (first Fibonacci number)
• F₂ = 1 (second Fibonacci number)
• Fₙ = Fₙ₋₁ + Fₙ₋₂ for n > 2 (each subsequent number is the sum of the two preceding ones)

So the sequence starts as: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

For example:

• If k = 7, you can use Fibonacci numbers 5 and 2 (both from the sequence), giving you 5 + 2 = 7. The answer would be 2 (two numbers used).
• If k = 10, you can use Fibonacci numbers 8 and 2, giving you 8 + 2 = 10. The answer would be 2.
• If k = 19, you can use Fibonacci numbers 13, 5, and 1, giving you 13 + 5 + 1 = 19. The answer would be 3.

The problem guarantees that for any given k, there will always be a valid combination of Fibonacci numbers that sum to k.

Intuition

The key insight is that we want to use as few Fibonacci numbers as possible. To minimize the count, we should try to use the largest possible Fibonacci numbers first. Think of it like making change with coins - if you want to use the fewest coins, you'd start with the largest denominations.

Why does this greedy approach work for Fibonacci numbers? There's a special property: any two consecutive Fibonacci numbers don't share common Fibonacci factors (except 1). This means when we pick the largest Fibonacci number b that doesn't exceed k, the remainder k - b will always be less than the previous Fibonacci number in the sequence.

For instance, if we have Fibonacci numbers a, b, c where b = a + previous and c = b + a, and we choose b as the largest number ≤ k, then k - b < a. This is because if k - b ≥ a, then k ≥ a + b = c, meaning we should have chosen c instead of b as our largest Fibonacci number.

This property ensures that once we pick a Fibonacci number, we won't need to pick the immediately preceding one in the sequence. This prevents overlap and guarantees that our greedy choice is optimal - we're always making progress toward zero without creating conflicts or needing to backtrack.

The algorithm naturally becomes: keep finding the largest Fibonacci number that fits into our remaining sum, subtract it, and repeat until we reach zero. Each subtraction uses one Fibonacci number, so we just count how many times we perform this operation.

Learn more about Greedy and Math patterns.

Solution Approach

The implementation follows the greedy strategy we identified. Here's how the algorithm works:

Step 1: Generate Fibonacci numbers up to k

a = b = 1
while b <= k:
    a, b = b, a + b

We start with a = 1 and b = 1 (the first two Fibonacci numbers). We keep generating the next Fibonacci number by updating b = a + b and shifting a = b. We continue this until b exceeds k. At this point, a contains the largest Fibonacci number that doesn't exceed k.

Step 2: Greedily subtract Fibonacci numbers from k

ans = 0
while k:
    if k >= b:
        k -= b
        ans += 1
    a, b = b - a, a

Now we work backwards through the Fibonacci sequence:

• If the current Fibonacci number b fits into k (i.e., k >= b), we subtract it from k and increment our answer counter
• We then move to the previous Fibonacci number by updating a, b = b - a, a
  • The new b becomes the old a
  • The new a becomes b - a, which gives us the Fibonacci number before the old a

This backward traversal is clever: since F(n) = F(n-1) + F(n-2), we can derive that F(n-2) = F(n) - F(n-1). So if we have two consecutive Fibonacci numbers a and b where b > a, the previous number in the sequence is b - a.

The algorithm continues until k becomes 0, at which point ans contains the minimum number of Fibonacci numbers needed.

Why this works optimally: As discussed in the intuition, when we select the largest Fibonacci number b that fits, the remainder is guaranteed to be less than the previous Fibonacci number a. This means we'll never select consecutive Fibonacci numbers, ensuring our greedy choice leads to the optimal solution without needing dynamic programming or backtracking.

Example Walkthrough

Let's walk through the algorithm with k = 19.

Step 1: Generate Fibonacci numbers up to 19

Starting with a = 1, b = 1:

• a = 1, b = 1 → Since b ≤ 19, continue
• a = 1, b = 2 (update: a, b = b, a + b)
• a = 2, b = 3
• a = 3, b = 5
• a = 5, b = 8
• a = 8, b = 13
• a = 13, b = 21 → Since 21 > 19, stop

We end with a = 13 (largest Fibonacci ≤ 19) and b = 21.

Step 2: Greedily subtract Fibonacci numbers

Starting with k = 19, ans = 0, and working backwards from b = 21, a = 13:

Iteration 1:

• Check: Is 19 ≥ 21? No, so don't use 21
• Move to previous Fibonacci: a, b = b - a, a → a = 8, b = 13

Iteration 2:

• Check: Is 19 ≥ 13? Yes!
• Subtract: k = 19 - 13 = 6, increment ans = 1
• Move to previous: a, b = 8 - 13, 8 → a = 5, b = 8

Iteration 3:

• Check: Is 6 ≥ 8? No
• Move to previous: a, b = 8 - 5, 5 → a = 3, b = 5

Iteration 4:

• Check: Is 6 ≥ 5? Yes!
• Subtract: k = 6 - 5 = 1, increment ans = 2
• Move to previous: a, b = 5 - 3, 3 → a = 2, b = 3

Iteration 5:

• Check: Is 1 ≥ 3? No
• Move to previous: a, b = 3 - 2, 2 → a = 1, b = 2

Iteration 6:

• Check: Is 1 ≥ 2? No
• Move to previous: a, b = 2 - 1, 1 → a = 1, b = 1

Iteration 7:

• Check: Is 1 ≥ 1? Yes!
• Subtract: k = 1 - 1 = 0, increment ans = 3

Since k = 0, we're done. The answer is 3.

We used the Fibonacci numbers: 13 + 5 + 1 = 19, requiring exactly 3 numbers.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log k)

The algorithm consists of two main phases:

1. First while loop - Generates Fibonacci numbers up to k. Since Fibonacci numbers grow exponentially (approximately φ^n where φ ≈ 1.618), the number of iterations needed to reach k is O(log k).

2. Second while loop - Uses a greedy approach to subtract the largest possible Fibonacci numbers from k. In each iteration, we either:

   • Subtract a Fibonacci number from k (reducing k significantly)
   • Move to the next smaller Fibonacci number

Since we're working backwards through the Fibonacci sequence and each subtraction reduces k substantially (due to the greedy property and Zeckendorf's theorem), the total number of iterations is also bounded by O(log k).

Therefore, the overall time complexity is O(log k) + O(log k) = O(log k).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables a and b to track Fibonacci numbers
• Variable ans to count the result
• Variable k (modifying the input parameter)

No additional data structures or recursive calls are used, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Fibonacci Sequence Generation Boundary

The Issue: A common mistake is generating Fibonacci numbers incorrectly by using while curr < k instead of while curr <= k. This causes the algorithm to stop one Fibonacci number too early.

# INCORRECT - stops too early
prev, curr = 1, 1
while curr < k:  # Wrong condition!
    prev, curr = curr, prev + curr

For example, if k = 8, this would stop when curr = 8, making curr advance to 13 in the next iteration outside the loop. We'd miss using 8 itself, which is the optimal choice.

The Fix: Use while curr <= k to ensure we generate all Fibonacci numbers up to and including k:

# CORRECT
prev, curr = 1, 1
while curr <= k:
    prev, curr = curr, prev + curr

Pitfall 2: Incorrect Backward Traversal of Fibonacci Sequence

The Issue: When moving backwards through the Fibonacci sequence, developers often mix up the order of operations or the assignment:

# INCORRECT - wrong order in tuple assignment
prev, curr = prev - curr, curr  # This doesn't give previous Fibonacci numbers!

# INCORRECT - trying to be too clever with the update
prev = curr - prev
curr = prev  # This uses the updated prev, not the original!

The Fix: Remember that if you have consecutive Fibonacci numbers prev and curr where curr > prev, the previous pair is (curr - prev, prev):

# CORRECT
prev, curr = curr - prev, prev

Pitfall 3: Not Handling Edge Cases Properly

The Issue: Forgetting to handle small values of k (like k = 1 or k = 2) might lead to unexpected behavior if the Fibonacci generation loop is written differently:

# PROBLEMATIC if modified incorrectly
def findMinFibonacciNumbers(self, k: int) -> int:
    if k == 0:  # Unnecessary check that might confuse
        return 0
  
    fibs = [1, 1]  # Using a list might lead to off-by-one errors
    while fibs[-1] < k:
        fibs.append(fibs[-1] + fibs[-2])
    # Now need to handle indexing carefully...

The Fix: The original algorithm naturally handles all cases including k = 1 without special conditions. Stick to the simple two-variable approach that works universally:

# CORRECT - handles all cases naturally
prev, curr = 1, 1
while curr <= k:
    prev, curr = curr, prev + curr
# Works for k = 1, 2, or any positive integer