JOIN

 Problem Statement

Problem Statement for FibonacciSum

### 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

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)

 `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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
2005 TCO Online Round 1 - Division I, Level Two
2005 TCO Sponsor Track Round 1 - Division I, Level Two