Tap here to switch tabs
Problem
Submissions

Problem: Minimum Number of Fibonacci Numbers Whose Sum Is K

Minimum Number of Fibonacci Numbers Whose Sum Is K asks you to return the fewest Fibonacci numbers that add up to a given positive integer, with repeated values allowed.

Statement

Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k. The same Fibonacci number may be used multiple times.

The Fibonacci numbers are defined as follows:

  • F1=1F_1 = 1

  • F2=1F_2 = 1

  • Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} for n≥3n \ge 3

Constraints:

  • 1≤1 \le k ≤109\le 10^9

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Number of Fibonacci Numbers Whose Sum Is K

Minimum Number of Fibonacci Numbers Whose Sum Is K asks you to return the fewest Fibonacci numbers that add up to a given positive integer, with repeated values allowed.

Statement

Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k. The same Fibonacci number may be used multiple times.

The Fibonacci numbers are defined as follows:

  • F1=1F_1 = 1

  • F2=1F_2 = 1

  • Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2} for n≥3n \ge 3

Constraints:

  • 1≤1 \le k ≤109\le 10^9