FibonacciSum
TCO05 Sponsor Rd 1 · 2005-08-16 · by AdminBrett
TCO05 Sponsor Rd 1 · 2005-08-16 · by AdminBrett · Dynamic Programming, Greedy
Problem Statement
Problem Statement
Depicted below is the Fibonacci sequence:
1, 1, 2, 3, 5, 8, 13, 21, 34, ...As you can see, each value from 2 on is the sum of the previous two values. Any positive integer can be written as a sum of values taken from the Fibonacci sequence. These values need not be distinct. Return the smallest number of such values that sum to n.
Constraints
- n will be between 1 and 1000000 inclusive.
Examples
0)
1 Returns: 1
Just a single number is required.
1)
7 Returns: 2
The best we can do is 5+2 = 7.
2)
70 Returns: 3
The best here is 34+34+2 = 70.
3)
1000000 Returns: 5
4)
999999 Returns: 8
Submissions are judged against all 85 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FibonacciSum with a public method int howMany(int n) · 85 test cases · 2 s / 256 MB per case