Problem

Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal tok. 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.

Examples

Example 1

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6
7


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

Example 3

1
2
3
4
5
6
7


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

Constraints

  • 1 <= k <= 10^9

Solution

Method 1 – Greedy (Zeckendorf’s Theorem)

Intuition

To represent a number as the sum of the minimum number of Fibonacci numbers, always subtract the largest Fibonacci number less than or equal to the current value. This is based on Zeckendorf’s theorem, which states every positive integer can be uniquely represented as the sum of non-consecutive Fibonacci numbers.

Approach

  1. Generate all Fibonacci numbers up to k.
  2. Start from the largest Fibonacci number and subtract it from k if it does not exceed k.
  3. Repeat the process, counting each subtraction, until k becomes 0.
  4. Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        vector<int> fib = {1, 1};
        while(fib.back() < k) fib.push_back(fib[fib.size()-1] + fib[fib.size()-2]);
        int ans = 0;
        for(int i = fib.size()-1; i >= 0 && k > 0; --i) {
            if(fib[i] <= k) {
                k -= fib[i];
                ++ans;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func findMinFibonacciNumbers(k int) int {
    fib := []int{1, 1}
    for fib[len(fib)-1] < k {
        fib = append(fib, fib[len(fib)-1]+fib[len(fib)-2])
    }
    ans := 0
    for i := len(fib)-1; i >= 0 && k > 0; i-- {
        if fib[i] <= k {
            k -= fib[i]
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int findMinFibonacciNumbers(int k) {
        List<Integer> fib = new ArrayList<>();
        fib.add(1); fib.add(1);
        while(fib.get(fib.size()-1) < k) fib.add(fib.get(fib.size()-1) + fib.get(fib.size()-2));
        int ans = 0;
        for(int i = fib.size()-1; i >= 0 && k > 0; --i) {
            if(fib.get(i) <= k) {
                k -= fib.get(i);
                ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun findMinFibonacciNumbers(k: Int): Int {
        val fib = mutableListOf(1, 1)
        while (fib.last() < k) fib.add(fib.last() + fib[fib.size-2])
        var ans = 0
        var kk = k
        for (i in fib.size-1 downTo 0) {
            if (fib[i] <= kk) {
                kk -= fib[i]
                ans++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fib = [1, 1]
        while fib[-1] < k:
            fib.append(fib[-1] + fib[-2])
        ans = 0
        for f in reversed(fib):
            if f <= k:
                k -= f
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn find_min_fibonacci_numbers(mut k: i32) -> i32 {
        let mut fib = vec![1, 1];
        while *fib.last().unwrap() < k {
            let n = fib.len();
            fib.push(fib[n-1] + fib[n-2]);
        }
        let mut ans = 0;
        for &f in fib.iter().rev() {
            if f <= k {
                k -= f;
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    findMinFibonacciNumbers(k: number): number {
        const fib = [1, 1];
        while (fib[fib.length-1] < k) fib.push(fib[fib.length-1] + fib[fib.length-2]);
        let ans = 0;
        for (let i = fib.length-1; i >= 0 && k > 0; --i) {
            if (fib[i] <= k) {
                k -= fib[i];
                ans++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(log k), since the number of Fibonacci numbers less than k is logarithmic in k.
  • 🧺 Space complexity: O(log k), for storing the Fibonacci sequence up to k.