Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Medium
1293.

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K is a medium coding problem on math and greedy, asked in Amazon and Microsoft interviews.

The Fibonacci numbers are F1 = 1, F2 = 1 and Fn = Fn-1 + Fn-2 for n > 2: 1, 1, 2, 3, 5, 8, 13, …

Given an integer k, return the minimum number of Fibonacci numbers whose sum is exactly k. The same Fibonacci number may be used more than once. Such a sum always exists.

Example 1

Input
k = 7
Output
2
Explanation
7 = 2 + 5.

Example 2

Input
k = 10
Output
2
Explanation
10 = 2 + 8.

Example 3

Input
k = 19
Output
3
Explanation
19 = 1 + 5 + 13.

Constraints

  • 1 <= k <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} k
 * @return {number}
 */
var findMinFibonacciNumbers = function(k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K Solution

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K is a medium coding problem on math and greedy, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Math, Greedy
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The Fibonacci numbers are F1 = 1, F2 = 1 and Fn = Fn-1 + Fn-2 for n > 2: 1, 1, 2, 3, 5, 8, 13, …

Given an integer k, return the minimum number of Fibonacci numbers whose sum is exactly k. The same Fibonacci number may be used more than once. Such a sum always exists.

Example 1

Input: k = 7
Output: 2
Explanation: 7 = 2 + 5.

Example 2

Input: k = 10
Output: 2
Explanation: 10 = 2 + 8.

Example 3

Input: k = 19
Output: 3
Explanation: 19 = 1 + 5 + 13.

Constraints

  • 1 <= k <= 10^9

Hints for Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

  1. Hint 1

    Try taking the largest Fibonacci number that does not exceed k, then repeat on what is left.

  2. Hint 2

    Why is that safe? An optimal sum never needs two consecutive Fibonacci numbers (replace them by their sum) nor the same number twice (2·Fn = Fn+1 + Fn-2).

  3. Hint 3

    A sum of non-consecutive, distinct Fibonacci numbers below F(m+1) cannot reach F(m+1), so the largest Fibonacci number ≤ k must be in it.

How to solve Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Greedy works: repeatedly subtract the largest Fibonacci number not exceeding the remainder (Zeckendorf's representation).

Approach

  1. List the Fibonacci numbers up to k.
  2. Walk the list from the largest: whenever the current number fits in the remainder, subtract it and count it.
  3. Stop when the remainder is 0 and return the count.

Why it works

Among optimal sums take one with the fewest terms that also avoids two consecutive Fibonacci numbers (merging Fn + Fn+1 into Fn+2 reduces the count) and repeated ones (2·Fn = Fn+1 + Fn-2 keeps the count but removes the repeat, and the process terminates). The largest possible sum of distinct, non-consecutive Fibonacci numbers all below F(m) is F(m) − 1, so if the largest Fibonacci number F(m) ≤ k were missing the terms could not reach k. Hence an optimal sum contains it, and induction on k − F(m) finishes the proof. After subtracting F(m) the remainder is below F(m−1), so the scan never needs to revisit a number.

Complexity

  • Time — O(log k) — there are about 44 Fibonacci numbers up to 10^9
  • Space — O(log k)

Pitfalls

  • A coin-change DP is correct but needs O(k) memory, impossible for 10^9.
  • Generating Fibonacci numbers past k: the next one after 701,408,733 is 1,134,903,170, still inside int32, but stop before overflowing.
  • The two leading 1s are the same value; one copy in the list is enough.

Reference solution

Python

def findMinFibonacciNumbers(k: int) -> int:
    fib = [1, 2]
    while fib[-1] + fib[-2] <= k:
        fib.append(fib[-1] + fib[-2])
    count = 0
    for f in reversed(fib):
        if f <= k:
            k -= f
            count += 1
            if k == 0:
                break
    return count

Java

public static int findMinFibonacciNumbers(int k) {
    List<Long> fib = new ArrayList<>();
    fib.add(1L);
    fib.add(2L);
    while (fib.get(fib.size() - 1) + fib.get(fib.size() - 2) <= k) fib.add(fib.get(fib.size() - 1) + fib.get(fib.size() - 2));
    long rest = k;
    int count = 0;
    for (int i = fib.size() - 1; i >= 0 && rest > 0; i--) {
        if (fib.get(i) <= rest) {
            rest -= fib.get(i);
            count++;
        }
    }
    return count;
}

C++

int findMinFibonacciNumbers(int k) {
    vector<long long> fib = {1, 2};
    while (fib[fib.size() - 1] + fib[fib.size() - 2] <= k) fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]);
    long long rest = k;
    int count = 0;
    for (int i = (int)fib.size() - 1; i >= 0 && rest > 0; i--) {
        if (fib[i] <= rest) {
            rest -= fib[i];
            count++;
        }
    }
    return count;
}

JavaScript

var findMinFibonacciNumbers = function(k) {
    var fib = [1, 2];
    while (fib[fib.length - 1] + fib[fib.length - 2] <= k) fib.push(fib[fib.length - 1] + fib[fib.length - 2]);
    var count = 0;
    for (var i = fib.length - 1; i >= 0 && k > 0; i--) {
        if (fib[i] <= k) {
            k -= fib[i];
            count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Greedy Algorithms