Small Fibonacci Number
This problem was taken from the Coursera Data Structures and Algorithms Specialization, specifically from the Algorithmic Toolbox Course, Week 2, that I’ve recently completed. If you are taking that course or plan to take that course, please don’t look ahead at the solution as it will be against the Honor Code and won’t do you any good.
Problem Introduction
The Fibonacci numbers are defined as follows: F(0)= 0, F(1) = 1, and F(i) = F(i−1) + F(i−2) for i ≥ 2.
Problem Description
Task: Given an integer n, find the nth Fibonacci number F(n) .
Input Format: The input consists of a single integer n.
Constraints: 0 ≤ n ≤ 45.
Output Format: Output F(n) .
Time Limits: C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit: 512 Mb.
What To Do
If you are using C++, Java, or Python, your goal is to replace a slow recursive algorithm by a fast iterative algorithm that can easily compute F(45) .
My Solution:
There are better ways to do this, like instead of storing all the Fibonacci sequence up-to n, just store the last two answers, i-e F(i-1) and F(i-2), and compute the next one using that, but that’s the one I submitted at that time and it got accepted.
If you can think of any other way to improve this algorithm or if you could point out something that you think I did wrong, you’re more than welcome to reach out to me by responding to this and pointing out the mistakes. If you like this solution, please hit the “Recommend” button below, it’ll mean a lot to me. Thanks.
