Question

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

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 {

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

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

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