Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1414.html

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

Given the number k, return the minimum number of Fibonacci numbers whose sum is equal to k, whether a Fibonacci number could 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 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 <= 10^9

Related Topics:
Array, Greedy

Solution 1. Greedy

We greedily find the maximum fibonacci number that is smaller or equal to k.

Assume it’s b, then f(k) = f(k-b) + 1. f(0) = 0.

// OJ: https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/
// Time: O(F(k)) where F(k) is the steps to compute the fibonacci number greater than k
// Space: O(1)
class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        if (k == 0) return 0;
        int a = 1, b = 1;
        while (a + b <= k) {
            int c = a + b;
            a = b;
            b = c;
        }
        return findMinFibonacciNumbers(k - b) + 1;
    }
};

  • class Solution {
    public int findMinFibonacciNumbers(int k) {
        TreeSet<Integer> set = new TreeSet<Integer>();
        set.add(0);
        set.add(1);
        int prev2 = 1, prev1 = 1;
        int num = 2;
        while (num <= k) {
            set.add(num);
            prev2 = prev1;
            prev1 = num;
            num = prev2 + prev1;
        }
        int count = 0;
        while (k > 0) {
            int fibo = set.floor(k);
            k -= fibo;
            count++;
        }
        return count;
    }
}

############

class Solution {
    public int findMinFibonacciNumbers(int k) {
        if (k < 2) {
            return k;
        }
        int a = 1, b = 1;
        while (b <= k) {
            b = a + b;
            a = b - a;
        }
        return 1 + findMinFibonacciNumbers(k - a);
    }
}

  • // OJ: https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/
// Time: O(F(k)) where F(k) is the steps to compute the fibonacci number greater than k
// Space: O(1)
class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        if (k == 0) return 0;
        int a = 1, b = 1;
        while (a + b <= k) {
            int c = a + b;
            a = b;
            b = c;
        }
        return findMinFibonacciNumbers(k - b) + 1;
    }
};

  • class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        def dfs(k):
            if k < 2:
                return k
            a = b = 1
            while b <= k:
                a, b = b, a + b
            return 1 + dfs(k - a)

        return dfs(k)

############

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fib = [1, 1]
        while fib[-1] < k:
            fib.append(fib[-1] + fib[-2])
        res = 0
        while k != 0:
            for i in range(len(fib) - 1, -1, -1):
                if fib[i] <= k:
                    k -= fib[i]
                    res += 1
                    break
        return res

  • func findMinFibonacciNumbers(k int) int {
	if k < 2 {
		return k
	}
	a, b := 1, 1
	for b <= k {
		a, b = b, a+b
	}
	return 1 + findMinFibonacciNumbers(k-a)
}

  • const arr = [
    1836311903, 1134903170, 701408733, 433494437, 267914296, 165580141,
    102334155, 63245986, 39088169, 24157817, 14930352, 9227465, 5702887,
    3524578, 2178309, 1346269, 832040, 514229, 317811, 196418, 121393, 75025,
    46368, 28657, 17711, 10946, 6765, 4181, 2584, 1597, 987, 610, 377, 233, 144,
    89, 55, 34, 21, 13, 8, 5, 3, 2, 1,
];

function findMinFibonacciNumbers(k: number): number {
    let res = 0;
    for (const num of arr) {
        if (k >= num) {
            k -= num;
            res++;
            if (k === 0) {
                break;
            }
        }
    }
    return res;
}


  • const FIB: [i32; 45] = [
    1836311903, 1134903170, 701408733, 433494437, 267914296, 165580141, 102334155, 63245986,
    39088169, 24157817, 14930352, 9227465, 5702887, 3524578, 2178309, 1346269, 832040, 514229,
    317811, 196418, 121393, 75025, 46368, 28657, 17711, 10946, 6765, 4181, 2584, 1597, 987, 610,
    377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1,
];

impl Solution {
    pub fn find_min_fibonacci_numbers(mut k: i32) -> i32 {
        let mut res = 0;
        for &i in FIB.into_iter() {
            if k >= i {
                k -= i;
                res += 1;
                if k == 0 {
                    break;
                }
            }
        }
        res
    }
}

All Problems

All Solutions