The Last Digit of a Large 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 last digit of the nth Fibonacci number F(n) (that is, F(n) mod 10).
Input Format: The input consists of a single integer n.
Constraints: 0 ≤ n ≤ 10 ^7.
Output Format: Output the last digit of 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.
Sample 1
Input:
3
Output:
2
Sample 2
Input:
327305
Output:
5
What To Do
Recall that Fibonacci numbers grow exponentially fast. For example, the 200th Fibonacci number equals 280571172992510140037611932413038677189525. Therefore, a solution like
F[0]=0
F[1]=1
for i=2 to n:
F[i]=F[i-1]+F[i-2]
print(F[n] mod 10)will turn out to be too slow, because as i grows the ith iteration of the loop computes the sum of longer and longer numbers. Also, for example, F(1000) does not fit into the standard C++ int type.
To overcome this difficulty, you may want to store in F[i] not the ith Fibonacci number itself, but just its last digit (that is, F(i) mod 10). Computing the last digit of F(i) is easy: it is just the last digit of the sum of the last digits of F(i−1) and F(i−2) :
F[i]=(F[i-1]+F[i-2]) mod 10This way, all F[i]’s are just digits, so they fit perfectly into any standard integer type, and computing a sum of F[i − 1] and F[i − 2] is performed very quickly.
My Solution:
Explanation:
Well there’s not much to say, as it is not a very tricky problem. I just implemented the algorithm that they suggested in What To Do section. Instead of storing the whole Fibonacci number, just store their modulus and calculate the next one using that.
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.
