LeetCode 1414 - Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Difficulty: 🟡 Medium
Topics: Math, Greedy

Solution

Problem Understanding

The problem asks us to find the minimum number of Fibonacci numbers whose sum equals a given integer k. Fibonacci numbers are a sequence where each number is the sum of the previous two, starting with 1 and 1. The input k is a positive integer up to 1 billion. The output is a single integer representing the smallest count of Fibonacci numbers that add up to exactly k. Importantly, the same Fibonacci number can be used multiple times, and the problem guarantees that such a sum always exists.

Key points include understanding that we are not generating all combinations of Fibonacci numbers, which would be inefficient. We also need to consider large values of k, which means a brute-force approach will be too slow. Edge cases to consider are when k itself is a Fibonacci number, when k is small, and when k requires many Fibonacci numbers to sum up.

Approaches

The brute-force approach would attempt to generate all subsets of Fibonacci numbers up to k and check which combination sums to k with the minimum length. This is correct but highly inefficient, as the number of subsets grows exponentially with the number of Fibonacci numbers, making it infeasible for k up to 10^9.

The key insight for an optimal solution is greedy: always pick the largest Fibonacci number less than or equal to the remaining k, subtract it from k, and repeat until k reaches zero. This works because of Zeckendorf's theorem, which states that every positive integer can be represented uniquely as the sum of non-consecutive Fibonacci numbers. By always taking the largest available Fibonacci number, we minimize the number of numbers used.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Generate all combinations of Fibonacci numbers to sum to k
Optimal	O(log k)	O(log k)	Greedy approach using largest Fibonacci number ≤ k repeatedly

Algorithm Walkthrough

Generate all Fibonacci numbers up to k. Start with 1, 1 and iteratively add the next Fibonacci number as the sum of the last two, stopping when the number exceeds k.
Initialize a counter to track the number of Fibonacci numbers used.
Iterate while k > 0. In each iteration, find the largest Fibonacci number less than or equal to k.
Subtract this Fibonacci number from k and increment the counter by 1.
Repeat step 3 until k becomes zero.
Return the counter as the minimum number of Fibonacci numbers whose sum equals k.

Why it works: By always choosing the largest possible Fibonacci number, we ensure that we are using the fewest numbers possible. The process is guaranteed to terminate because Fibonacci numbers grow exponentially, reducing k efficiently at each step.

Python Solution

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fibs = [1, 1]
        while fibs[-1] < k:
            fibs.append(fibs[-1] + fibs[-2])
        
        count = 0
        idx = len(fibs) - 1
        while k > 0:
            if fibs[idx] <= k:
                k -= fibs[idx]
                count += 1
            idx -= 1
        
        return count

The Python solution first generates the Fibonacci sequence up to k. It then iterates from the largest Fibonacci number downward, subtracting numbers from k whenever they are less than or equal to the current value of k. Each subtraction increases the count. This implements the greedy algorithm exactly as described.

Go Solution

func findMinFibonacciNumbers(k int) int {
    fibs := []int{1, 1}
    for fibs[len(fibs)-1] < k {
        fibs = append(fibs, fibs[len(fibs)-1]+fibs[len(fibs)-2])
    }

    count := 0
    idx := len(fibs) - 1
    for k > 0 {
        if fibs[idx] <= k {
            k -= fibs[idx]
            count++
        }
        idx--
    }
    
    return count
}

In Go, we use a slice to store Fibonacci numbers up to k. The algorithm logic mirrors Python, using a loop to subtract the largest Fibonacci number available. Care is taken to handle slice indexing safely. Go does not have integer overflow issues for k up to 10^9 since int is large enough on most platforms.

Worked Examples

Example 1: k = 7

Fibonacci numbers ≤ 7: [1, 1, 2, 3, 5]

Steps: subtract 5 → k = 2, subtract 2 → k = 0. Count = 2

Example 2: k = 10

Fibonacci numbers ≤ 10: [1, 1, 2, 3, 5, 8]

Steps: subtract 8 → k = 2, subtract 2 → k = 0. Count = 2

Example 3: k = 19

Fibonacci numbers ≤ 19: [1, 1, 2, 3, 5, 8, 13]

Steps: subtract 13 → k = 6, subtract 5 → k = 1, subtract 1 → k = 0. Count = 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log k)	Fibonacci numbers grow exponentially, so there are O(log k) numbers ≤ k; iterating through them is proportional
Space	O(log k)	Storing Fibonacci numbers up to k requires O(log k) space

The logarithmic growth comes from the property that Fibonacci numbers grow roughly exponentially according to the golden ratio.

Test Cases

# Provided examples
assert Solution().findMinFibonacciNumbers(7) == 2  # 5 + 2
assert Solution().findMinFibonacciNumbers(10) == 2  # 8 + 2
assert Solution().findMinFibonacciNumbers(19) == 3  # 13 + 5 + 1

# Edge cases
assert Solution().findMinFibonacciNumbers(1) == 1  # smallest Fibonacci number
assert Solution().findMinFibonacciNumbers(2) == 1  # 2 is Fibonacci number
assert Solution().findMinFibonacciNumbers(1000000000) > 0  # large k, tests performance

# Cases where k is sum of several small numbers
assert Solution().findMinFibonacciNumbers(4) == 2  # 3 + 1
assert Solution().findMinFibonacciNumbers(6) == 2  # 5 + 1

Test	Why
k = 7	Checks normal combination of Fibonacci numbers
k = 10	Checks greedy selection with mid-sized k
k = 19	Checks multiple Fibonacci numbers required
k = 1	Checks minimum input
k = 2	Checks Fibonacci number itself
k = 10^9	Tests efficiency and large input
k = 4, 6	Tests sums of small Fibonacci numbers

Edge Cases

One edge case is when k is exactly a Fibonacci number. The greedy algorithm handles this correctly by selecting k itself in the first iteration, giving a count of 1.

Another edge case is small values of k, such as 1 or 2. The algorithm generates Fibonacci numbers up to k and can immediately select the largest one, which is the number itself.

A third edge case is when k is a sum of multiple Fibonacci numbers, requiring the algorithm to iteratively subtract the largest possible number. This tests whether the loop correctly handles multiple iterations and decrements k accurately. The algorithm guarantees correctness because it always reduces k with the largest valid Fibonacci number.