209. Fibonacci
Core1000 ms256 MBSolved by 0%
Print the nth Fibonacci number, where F(0) = 0, F(1) = 1, and every
later value is the sum of the two before it.
Write the obvious recursion first:
fib(n) = fib(n-1) + fib(n-2)
Then run it with n = 45 and time it. It is correct and it recomputes the
same values over and over: fib(40) alone makes about 331 million calls,
because fib(38) is worked out twice, fib(37) three times, fib(36)
five times, and so on down.
The fix is one line, and this problem exists so you write it yourself.
Constraints - `0 ≤ n ≤ 90` - The answer fits in a signed 64-bit integer.
Input
A single line containing one integer n.
Output
Print one integer, the nth Fibonacci number.
Input10
Output55
Noteis small enough to check against the sequence
Input0
Output0
Noteis the first base case, which is 0 rather than 1
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.