Last Digit of Fibonacci Number

Last Digit of Large Fibonacci Number

You will be given an integer n. Your task is to find the last digit of the n-th Fibonacci number. Remember that the Fibonacci numbers grow exponentially.

Constraints:

0 <= n <= 10 ⁷

Example

Input: 331 Output: 9

Hint View Explanation View Code

As the Fibonnaci Number gets very big quickly, it will be very slow to calculate the Fibonnaci number first and then calculate the last digit. Also the upper bound of the constraint is 10⁷ whose Fibonnaci number will not fit into memory.
To get the last digit of a number, number % 10

How to solve this problem?

Instead of storing the Fibonnaci numbers, find the last digit of the Fibonnaci number and store into variable.

big-O Analysis

My implementation takes O(n) time.