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

Math Greedy Medium

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:

F₁ = 1
F₂ = 1
F_n = F_n-1 + F_n-2 for n > 2

It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to k.

Input & Output

Example 1 — Basic Case

$ Input: k = 7

› Output: 2

💡 Note: The Fibonacci numbers are 1, 1, 2, 3, 5, 8... We can represent 7 as 5 + 2, so we need minimum 2 Fibonacci numbers

Example 2 — Single Number

$ Input: k = 8

› Output: 1

💡 Note: 8 is already a Fibonacci number, so we only need 1 Fibonacci number

Example 3 — Larger Number

$ Input: k = 15

› Output: 2

💡 Note: 15 can be represented as 13 + 2, requiring 2 Fibonacci numbers

Constraints

1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 f Facebook 12

The key insight is using Zeckendorf's theorem - every positive integer has a unique representation as sum of non-consecutive Fibonacci numbers. The greedy approach works optimally: always pick the largest Fibonacci number that fits. Time: O(log k), Space: O(log k)

Common Approaches

✓ Greedy Approach

⏱️ Time: O(log k) Space: O(log k)

Generate all Fibonacci numbers up to k, then greedily select the largest Fibonacci number that doesn't exceed the remaining sum. This works due to Zeckendorf's theorem.

Recursive Brute Force

⏱️ Time: O(2^n) Space: O(n)

Generate Fibonacci numbers up to k, then use recursion to try all possible combinations. For each Fibonacci number, either include it or skip it, and find the minimum count.

Greedy Approach — Algorithm Steps

Generate Fibonacci numbers ≤ k
Pick largest Fibonacci ≤ remaining sum
Subtract and repeat until sum is 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create Fibonacci sequence up to k

Pick Largest

Select largest Fibonacci ≤ remaining sum

Repeat

Continue until sum becomes 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int solution(int k) {
    if (k == 0) return 0;
    
    int fibs[50];
    int fibCount = 0;
    int a = 1, b = 1;
    while (a <= k) {
        fibs[fibCount++] = a;
        int temp = b;
        b = a + b;
        a = temp;
    }
    
    int count = 0;
    int i = fibCount - 1;
    
    while (k > 0) {
        if (fibs[i] <= k) {
            k -= fibs[i];
            count++;
        } else {
            i--;
        }
    }
    
    return count;
}

int main() {
    int k;
    scanf("%d", &k);
    printf("%d\n", solution(k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log k)

Generating Fibonacci numbers takes O(log k) since Fibonacci grows exponentially, and greedy selection also takes O(log k)

⚠ Quadratic Growth

Space Complexity

O(log k)

Storing Fibonacci numbers up to k requires O(log k) space

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler