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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Number: 1515

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an integer k, find the minimum number of Fibonacci numbers whose sum equals k. The Fibonacci numbers are defined as F₁ = 1, F₂ = 1, and for n > 2, Fₙ = Fₙ₋₁ + Fₙ₋₂. It is allowed to use the same Fibonacci number multiple times. It is guaranteed that such a representation exists.

Key Insights

  • Fibonacci numbers grow exponentially, so there are only O(log k) numbers less than or equal to k.
  • A greedy strategy works: always subtract the largest Fibonacci number from k until k becomes 0.
  • The problem guarantees a solution exists, ensuring the greedy approach is optimal for this scenario.

Space and Time Complexity

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

Solution

  1. Generate all Fibonacci numbers less than or equal to k.
  2. Iterate over the generated Fibonacci numbers in reverse order (from largest to smallest).
  3. For each Fibonacci number, determine how many times it can be subtracted from k and add that count to your answer.
  4. Subtract the appropriate amount from k and continue until k becomes 0.
  5. The sum of counts is the minimum number of Fibonacci numbers required.

This greedy approach works because using the largest possible Fibonacci numbers minimizes the number of terms needed to sum up to k.

Code Solutions

# Python implementation for finding the minimum number of Fibonacci numbers whose sum is k.

def findMinFibonacciNumbers(k):
    # Generate all Fibonacci numbers <= k
    fibs = [1, 1]
    while fibs[-1] < k:
        fibs.append(fibs[-1] + fibs[-2])
    
    # Initialize count of Fibonacci numbers used
    count = 0
    # Process Fibonacci numbers in reverse order
    for fib in reversed(fibs):
        if k == 0:
            break
        # If current Fibonacci number is less than or equal to k
        if fib <= k:
            # Calculate how many times this Fibonacci number fits into k
            times = k // fib
            count += times
            k -= fib * times
            
    return count

# Example usage:
# print(findMinFibonacciNumbers(7))  # Output: 2
← Back to All Questions