# UVa 10183

## Contents

## 10183 - How many Fibs?[edit]

## Summary[edit]

A pretty ordinary BigNum problem.

## Explanation[edit]

Generate the Fibonacci sequence until the last number generated exceeds and store it an array. It ends up taking about *480* numbers.

## Gotcha's[edit]

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*.

## Notes[edit]

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*.

## Optimizations[edit]

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.

## Solutions[edit]

## Input[edit]

0 1 1 1 10 100 1234567890 9876543210 0 0

## Output[edit]

1 1 5 4