Skip to content

1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Description

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

Solutions

Solution 1: Greedy

Thinking

\(k\le 10^9\) makes an unbounded-knapsack search over Fibonacci numbers unnecessary. Every positive integer has a Zeckendorf representation as a sum of distinct Fibonacci numbers.

Repeatedly subtract the largest Fibonacci number \(\le k\). If the previous term could still be used, a larger next term would have been chosen instead. Generate up to just past \(k\), then walk backward.

We can greedily select the largest Fibonacci number that does not exceed \(k\) each time, then subtract this number from \(k\) and increment the answer by one. This process is repeated until \(k = 0\).

Since we greedily select the largest Fibonacci number that does not exceed \(k\) each time, suppose this number is \(b\), the previous number is \(a\), and the next number is \(c\). Subtracting \(b\) from \(k\) results in a value that is less than \(a\), which means that after selecting \(b\), we will not select \(a\). This is because if we could select \(a\), then we could have greedily selected the next Fibonacci number \(c\) instead of \(b\) earlier, which contradicts our assumption. Therefore, after selecting \(b\), we can greedily reduce the Fibonacci number.

The time complexity is \(O(\log k)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        a = b = 1
        while b <= k:
            a, b = b, a + b
        ans = 0
        while k:
            if k >= b:
                k -= b
                ans += 1
            a, b = b - a, a
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int findMinFibonacciNumbers(int k) {
        int a = 1, b = 1;
        while (b <= k) {
            int c = a + b;
            a = b;
            b = c;
        }
        int ans = 0;
        while (k > 0) {
            if (k >= b) {
                k -= b;
                ++ans;
            }
            int c = b - a;
            b = a;
            a = c;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        int a = 1, b = 1;
        while (b <= k) {
            int c = a + b;
            a = b;
            b = c;
        }
        int ans = 0;
        while (k > 0) {
            if (k >= b) {
                k -= b;
                ++ans;
            }
            int c = b - a;
            b = a;
            a = c;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func findMinFibonacciNumbers(k int) (ans int) {
    a, b := 1, 1
    for b <= k {
        c := a + b
        a = b
        b = c
    }

    for k > 0 {
        if k >= b {
            k -= b
            ans++
        }
        c := b - a
        b = a
        a = c
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function findMinFibonacciNumbers(k: number): number {
    let [a, b] = [1, 1];
    while (b <= k) {
        let c = a + b;
        a = b;
        b = c;
    }

    let ans = 0;
    while (k > 0) {
        if (k >= b) {
            k -= b;
            ans++;
        }
        let c = b - a;
        b = a;
        a = c;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn find_min_fibonacci_numbers(mut k: i32) -> i32 {
        let mut a = 1;
        let mut b = 1;
        while b <= k {
            let c = a + b;
            a = b;
            b = c;
        }

        let mut ans = 0;
        while k > 0 {
            if k >= b {
                k -= b;
                ans += 1;
            }
            let c = b - a;
            b = a;
            a = c;
        }
        ans
    }
}

Comments