Skip to content

Latest commit

 

History

History
179 lines (145 loc) · 4.06 KB

README_EN.md

File metadata and controls

179 lines (145 loc) · 4.06 KB
Raw

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

Python3

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)

Java

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);
    }
}

TypeScript

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;
}

Rust

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
    }
}

C++

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);
    }
};

Go

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)
}

...