Taro Logo

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Medium
Asked by:
Profile picture
47 views
Topics:
Greedy AlgorithmsDynamic Programming

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.

The Fibonacci numbers are defined as:

  • F1 = 1
  • F2 = 1
  • Fn = Fn-1 + Fn-2 for n > 2.
It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to k.

Example 1:

Input: k = 7
Output: 2 
Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... 
For k = 7 we can use 2 + 5 = 7.

Example 2:

Input: k = 10
Output: 2 
Explanation: For k = 10 we can use 2 + 8 = 10.

Example 3:

Input: k = 19
Output: 3 
Explanation: For k = 19 we can use 1 + 5 + 13 = 19.

Constraints:

  • 1 <= k <= 109
Try coding it in LeetCodeLeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the maximum possible value of K, and is K guaranteed to be non-negative?
  2. If K is 0, what should I return?
  3. Should I return the *minimum* number of Fibonacci numbers, or just *a* set of Fibonacci numbers that sum to K?
  4. Are we using the standard Fibonacci sequence (1, 1, 2, 3, 5, ...), or does the sequence potentially start with different initial values?
  5. Are there any specific constraints on the data type of the Fibonacci numbers used (e.g., can they be very large, potentially requiring a `BigInteger` type)?

Brute Force Solution

Approach

We want to find the fewest Fibonacci numbers that add up to a specific target number. The brute force approach tries out absolutely every combination of Fibonacci numbers to see if it equals the target. We then pick the combination that uses the fewest numbers.

Here's how the algorithm would work step-by-step:

  1. First, generate a list of Fibonacci numbers that are less than or equal to our target number. We only need these because larger Fibonacci numbers can't possibly be part of the sum.
  2. Start by checking if just one Fibonacci number can add up to the target. Is the target itself a Fibonacci number?
  3. If not, then check if any combination of two Fibonacci numbers from our list add up to the target. Try every possible pair.
  4. If no pair works, then check all combinations of three Fibonacci numbers. Keep trying larger combinations (four, five, etc.) until you either find a solution or you've exhausted all the possibilities.
  5. As you check each combination, keep track of how many Fibonacci numbers you used.
  6. Once you find a combination that adds up to the target, remember how many Fibonacci numbers it used.
  7. Continue searching through all the other combinations of Fibonacci numbers, even after you find a solution.
  8. If you find another combination that adds up to the target using even fewer Fibonacci numbers than before, replace your previous answer with this new one.
  9. In the end, the solution will be the combination that used the absolute fewest Fibonacci numbers to reach the target.

Code Implementation

def find_minimum_fibonacci_numbers_whose_sum_is_k(k):
    fibonacci_numbers = [1, 1]
    while fibonacci_numbers[-1] <= k:
        fibonacci_numbers.append(fibonacci_numbers[-1] + fibonacci_numbers[-2])
    fibonacci_numbers.pop()

    minimum_count = float('inf')

    for i in range(1 << len(fibonacci_numbers)):
        current_sum = 0
        current_count = 0
        combination = []

        for j in range(len(fibonacci_numbers)):
            if (i >> j) & 1:
                current_sum += fibonacci_numbers[j]
                current_count += 1
                combination.append(fibonacci_numbers[j])

        # Check if the sum matches the target
        if current_sum == k:

            # Update minimum count if necessary
            minimum_count = min(minimum_count, current_count)

    return minimum_count

Big(O) Analysis

Time Complexity
O(k^c) – The described brute force approach first generates Fibonacci numbers up to k. Let's assume there are approximately c such numbers (c grows logarithmically with k, but in the worst case we iterate through all of them). The algorithm then iterates through all combinations of these Fibonacci numbers to find a sum equal to k. In the absolute worst-case scenario, where no optimization is performed and the number of Fibonacci numbers required is large, the algorithm checks all possible subsets which can approach O(k^c), where c is the number of fibonacci numbers we can use, since the number of combinations will depend on k. Thus, the overall time complexity is exponential, approximately O(k^c).
Space Complexity
O(K) – The algorithm first generates a list of Fibonacci numbers less than or equal to the target number K. This list is stored in memory, contributing to auxiliary space. In the worst case, the number of Fibonacci numbers less than or equal to K can be proportional to K. Therefore, the space complexity is O(K).

Optimal Solution

Approach

The core idea is to use the largest possible Fibonacci numbers first to quickly reduce the target sum. We find the largest Fibonacci number less than or equal to our target and subtract it, repeating this process until we reach zero. The number of Fibonacci numbers we used represents the minimum count.

Here's how the algorithm would work step-by-step:

  1. Generate a list of Fibonacci numbers that are less than or equal to the target number.
  2. Start with the target number.
  3. Find the largest Fibonacci number in the list that is less than or equal to the current target number.
  4. Subtract this Fibonacci number from the current target number.
  5. Increment a counter to track the number of Fibonacci numbers used.
  6. Repeat steps 3-5 until the target number becomes zero.
  7. The final counter value is the minimum number of Fibonacci numbers needed.

Code Implementation

def find_min_fibonacci_numbers(target_number):
    fibonacci_numbers = [1, 1]
    while fibonacci_numbers[-1] <= target_number:
        next_fibonacci = fibonacci_numbers[-1] + fibonacci_numbers[-2]
        fibonacci_numbers.append(next_fibonacci)

    fibonacci_numbers.pop()

    number_of_fibonacci_numbers = 0
    remaining_sum = target_number

    while remaining_sum > 0:
        # Find the largest Fibonacci number <= remaining sum.
        largest_fibonacci_index = 0

        for i in range(len(fibonacci_numbers)):
            if fibonacci_numbers[i] <= remaining_sum:
                largest_fibonacci_index = i
            else:
                break

        # Use the largest possible Fibonacci number.
        remaining_sum -= fibonacci_numbers[largest_fibonacci_index]

        number_of_fibonacci_numbers += 1

    return number_of_fibonacci_numbers

Big(O) Analysis

Time Complexity
O(log K) – The time complexity is determined by two main factors: generating the Fibonacci numbers and the process of subtracting the largest possible Fibonacci number from K until K reaches zero. Generating the Fibonacci numbers takes O(log K) time because the number of Fibonacci numbers less than or equal to K grows logarithmically with K. The subtraction process also takes O(log K) time, as we are essentially iterating through the generated Fibonacci numbers, whose count is logarithmic to K, to find the largest one less than or equal to the current target. Therefore, the overall time complexity is O(log K).
Space Complexity
O(log K) – The space complexity is dominated by the list of Fibonacci numbers generated, which are less than or equal to K. The number of Fibonacci numbers required to reach a value close to K grows logarithmically with K because each Fibonacci number is roughly a constant multiple of the previous one. Therefore, the list of Fibonacci numbers stores approximately log K elements, resulting in O(log K) auxiliary space.

Edge Cases

K is 0
How to Handle:
Return 0 as no Fibonacci numbers are needed to sum to 0.
K is 1
How to Handle:
Return 1 as the first Fibonacci number is 1.
K is a Fibonacci number
How to Handle:
Return 1, as K itself can be the only number needed.
K is a very large number (close to integer limit)
How to Handle:
Ensure Fibonacci number generation doesn't cause integer overflow, potentially using long data type.
When generating Fibonacci numbers, potential for integer overflow before reaching K
How to Handle:
Use a data type with sufficient capacity (e.g., long) or stop generating Fibonacci numbers when the next number exceeds K.
K is a negative number
How to Handle:
Return an error or throw an exception as Fibonacci numbers are positive and cannot sum to a negative number.
Generating a very long Fibonacci sequence that is never used.
How to Handle:
Optimize Fibonacci number generation to stop once the largest Fibonacci number is greater than K.
Greedy approach fails if not picking largest Fibonacci number smaller than K at each step.
How to Handle:
Ensure the algorithm correctly identifies and picks the largest suitable Fibonacci number at each iteration to guarantee the minimum count.
Taro Footer Icon
Taro Footer Logo
Explore Interview QuestionsTaro 75Google Interview QuestionsMeta Interview QuestionsAmazon Interview QuestionsApple Interview QuestionsNetflix Interview Questions
Explore Interview ExperiencesOpenAI Interview ExperiencesAnthropic Interview ExperiencesPerplexity Interview ExperiencesWindsurf Interview ExperiencesMistral AI Interview Experiences
Explore TrendingLayoffsPerformance Improvement PlanSystem DesignInterpersonal CommunicationTech Lead
ProductGreat DiscussionsPerksTopics
CompanyPrivacy PolicyTerms & ConditionsSupport
Taro iOS appTaro Android app
LinkedIn IconTwitter IconYouTube Icon
Copyright © Taro