FibonacciSum | Topcoder Archive

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.

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.
```
107
```
```
Returns: 3
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.