Problem Statement
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.
Definition
- Class:
- FibonacciSum
- Method:
- howMany
- Parameters:
- int
- Returns:
- int
- Method signature:
- int howMany(int n)
- (be sure your method is public)
Constraints
- n will be between 1 and 1000000 inclusive.
Examples
1
Returns: 1
Just a single number is required.
7
Returns: 2
The best we can do is 5+2 = 7.
70
Returns: 3
The best here is 34+34+2 = 70.
1000000
Returns: 5
999999
Returns: 8
2
Returns: 1
3
Returns: 1
4
Returns: 2
5
Returns: 1
6
Returns: 2
8
Returns: 1
9
Returns: 2
10
Returns: 2
11
Returns: 2
12
Returns: 3
13
Returns: 1
14
Returns: 2
15
Returns: 2
16
Returns: 2
17
Returns: 3
18
Returns: 2
19
Returns: 3
20
Returns: 3
21
Returns: 1
999998
Returns: 8
999997
Returns: 7
999996
Returns: 8
999995
Returns: 7
999994
Returns: 7
999993
Returns: 7
999992
Returns: 6
999991
Returns: 8
999990
Returns: 7
999989
Returns: 7
240902
Returns: 7
918284
Returns: 7
865065
Returns: 7
270670
Returns: 10
267570
Returns: 9
707025
Returns: 10
849860
Returns: 6
798082
Returns: 9
50960
Returns: 4
520498
Returns: 8
518827
Returns: 6
776432
Returns: 9
34861
Returns: 7
726516
Returns: 9
702071
Returns: 10
996511
Returns: 10
723975
Returns: 9
618373
Returns: 8
70218
Returns: 8
527869
Returns: 5
107
Returns: 3
832040
Returns: 1
2584
Returns: 1
2585
Returns: 2
4181
Returns: 1
4182
Returns: 2
6765
Returns: 1
6766
Returns: 2
10946
Returns: 1
10947
Returns: 2
17711
Returns: 1
17712
Returns: 2
28657
Returns: 1
28658
Returns: 2
46368
Returns: 1
46369
Returns: 2
75025
Returns: 1
75026
Returns: 2
121393
Returns: 1
121394
Returns: 2
196418
Returns: 1
196419
Returns: 2
999003
Returns: 10
999999
Returns: 8
1000000
Returns: 5
107
Returns: 3
514228
Returns: 14
832040
Returns: 1
992781
Returns: 12
271442
Returns: 13
999998
Returns: 8