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

Approach 1: Recursive

• Time: $O((\log k)^2)$
• Space: $O(\log k)$

C++JavaPython

class Solution {
 public:
  int findMinFibonacciNumbers(int k) {
    if (k < 2)  // k == 0 || k == 1
      return k;

    int a = 1;  // F_1
    int b = 1;  // F_2

    while (b <= k) {
      //    a, b = F_{i + 1}, F_{i + 2}
      // -> a, b = F_{i + 2}, F_{i + 3}
      const int temp = a;
      a = b;
      b = a + temp;
    }

    return 1 + findMinFibonacciNumbers(k - a);
  }
};

class Solution {
  public int findMinFibonacciNumbers(int k) {
    if (k < 2) // k == 0 || k == 1
      return k;

    int a = 1; // F_1
    int b = 1; // F_2

    while (b <= k) {
      //    a, b = F_{i + 1}, F_{i + 2}
      // -> a, b = F_{i + 2}, F_{i + 3}
      final int temp = a;
      a = b;
      b = a + temp;
    }

    return 1 + findMinFibonacciNumbers(k - a);
  }
}

class Solution:
  def findMinFibonacciNumbers(self, k: int) -> int:
    if k < 2:  # k == 0 or k == 1
      return k

    a = 1  # F_1
    b = 1  # F_2

    while b <= k:
      #    a, b = F_{i + 1}, F_{i + 2}
      # -> a, b = F_{i + 2}, F_{i + 3}
      a, b = b, a + b

    return 1 + self.findMinFibonacciNumbers(k - a)

Approach 2: Iterative

• Time: $O(\log k)$
• Space: $O(1)$

C++JavaPython

class Solution {
 public:
  int findMinFibonacciNumbers(int k) {
    int ans = 0;
    int a = 1;  // F_1
    int b = 1;  // F_2

    while (b <= k) {
      //    a, b = F_{i + 1}, F_{i + 2}
      // -> a, b = F_{i + 2}, F_{i + 3}
      const int temp = a;
      a = b;
      b = a + temp;
    }

    while (a > 0) {
      if (a <= k) {
        k -= a;
        ++ans;
      }
      //    a, b = F_{i + 2}, F_{i + 3}
      // -> a, b = F_{i + 1}, F_{i + 2}
      const int temp = a;
      a = b - a;
      b = temp;
    }

    return ans;
  }
};

class Solution {
  public int findMinFibonacciNumbers(int k) {
    int ans = 0;
    int a = 1; // F_1
    int b = 1; // F_2

    while (b <= k) {
      //    a, b = F_{i + 1}, F_{i + 2}
      // -> a, b = F_{i + 2}, F_{i + 3}
      final int temp = a;
      a = b;
      b = a + temp;
    }

    while (a > 0) {
      if (a <= k) {
        k -= a;
        ++ans;
      }
      //    a, b = F_{i + 2}, F_{i + 3}
      // -> a, b = F_{i + 1}, F_{i + 2}
      final int temp = a;
      a = b - a;
      b = temp;
    }

    return ans;
  }
}

class Solution:
  def findMinFibonacciNumbers(self, k: int) -> int:
    ans = 0
    a = 1  # F_1
    b = 1  # F_2

    while b <= k:
      #    a, b = F_{i + 1}, F_{i + 2}
      # -> a, b = F_{i + 2}, F_{i + 3}
      a, b = b, a + b

    while a > 0:
      if a <= k:
        k -= a
        ans += 1
      #    a, b = F_{i + 2}, F_{i + 3}
      # -> a, b = F_{i + 1}, F_{i + 2}
      a, b = b - a, a

    return ans