We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Difficulty: Medium

Problem Description

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.

Key Insights

  • Fibonacci numbers grow rapidly, allowing for efficient summation.
  • The greedy approach can be utilized: always subtract the largest possible Fibonacci number from k.
  • The problem guarantees a solution exists for the given constraints.

Space and Time Complexity

Time Complexity: O(log k) - The number of Fibonacci numbers grows logarithmically in relation to k. Space Complexity: O(1) - We only need a few variables to store Fibonacci numbers and the count.

Solution

To solve this problem, we can use a greedy algorithm. We will generate Fibonacci numbers until we exceed k, and then, starting from the largest Fibonacci number, we will subtract it from k as many times as possible until k becomes zero. Each subtraction corresponds to using one Fibonacci number, which allows us to count how many Fibonacci numbers are needed to sum up to the original k.

  1. Generate all Fibonacci numbers that are less than or equal to k.
  2. Start from the largest Fibonacci number and subtract it from k until k becomes zero, counting how many numbers we used.

This approach ensures that we use the minimum number of Fibonacci numbers due to the greedy selection of the largest available number.

Code Solutions

def findMinFibonacciNumbers(k):
    # Generate Fibonacci numbers up to k
    fib = [1, 1]
    while fib[-1] <= k:
        fib.append(fib[-1] + fib[-2])
    
    count = 0
    # Start from the largest Fibonacci number
    for i in range(len(fib) - 1, -1, -1):
        if k == 0:
            break
        if fib[i] <= k:
            k -= fib[i]
            count += 1
            
    return count
← Back to All Questions