10183 - How many Fibs?
A pretty ordinary BigNum problem.
Generate the Fibonacci sequence until the last number generated exceeds and store it an array. It ends up taking about 480 numbers.
The first number input may be 0. Note that the problem defines a fairly non-standard sequence, where the first two numbers in the sequence aren't both 1, but rather 1 and 2.
The Fibonacci numbers increase by approximately a factor of . Thus, there are O(d) Fibonacci numbers with less than or equal to d digits. The exact constant multiple hidden by the O is . This would predict that we would need 478 numbers to store the Fibonacci numbers with less than 100 digits, when we actually used 480.
Since we never have to through more than 500 numbers, and the size of the numbers, about 100 digits, is near the size of the sequence itself, a linear search or two find the correct lower and upper indices in the sequence is sufficient to pass the time limit. However, a binary search will yield a lower time.
0 1 1 1 10 100 1234567890 9876543210 0 0
1 1 5 4