Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

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: 3

💡 Note: 15 can be represented as 8 + 5 + 2, requiring 3 Fibonacci numbers

Constraints

1 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Given k=15, find minimum Fibonacci numbers

Process

Use greedy: pick largest Fibonacci ≤ k

Output

Count of numbers needed: 3

Key Takeaway

🎯 Key Insight: Greedy works because of Zeckendorf's theorem - always pick the largest Fibonacci number that fits

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

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(2^n)	O(n)	Try all possible combinations of Fibonacci numbers recursively
Greedy Approach	O(log k)	O(log k)	Always pick the largest Fibonacci number that fits, then repeat

Recursive Brute Force — Algorithm Steps

Generate all Fibonacci numbers ≤ k
Use recursion to try all combinations
Return minimum count found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Fibs

Create list [1,1,2,3,5,8] for k=15

Recursive Tree

For each fib number, try include/exclude

Find Minimum

Return path with minimum count

Code -

solution.c — C

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

int dfs(int* fibs, int fibCount, int idx, int remaining) {
    if (remaining == 0) return 0;
    if (idx >= fibCount || remaining < 0) return INT_MAX;
    
    int skip = dfs(fibs, fibCount, idx + 1, remaining);
    int take = dfs(fibs, fibCount, idx, remaining - fibs[idx]);
    if (take != INT_MAX) take++;
    
    return skip < take ? skip : take;
}

int solution(int k) {
    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;
    }
    
    return dfs(fibs, fibCount, 0, k);
}

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

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

For each Fibonacci number, we have 2 choices (include or exclude), leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and storing Fibonacci numbers

⚡ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler