Find the minimum number of fibonacci numbers whose sum is k

Math Greedy

64.8% acceptance

Feb 25, 2026

1051

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_min_fibonacci_numbers(mut k: i32) -> i32 {
    let mut fibs = vec![1i32, 1];
    while *fibs.last().unwrap() < k {
      let n = fibs.len();
      fibs.push(fibs[n-1] + fibs[n-2]);
    }
    let mut count = 0;
    while k > 0 {
      let pos = fibs.partition_point(|&x| x <= k);
      k -= fibs[pos - 1];
      count += 1;
    }
    count
  }
}