Get Time

   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