Solution: Last Digit of Fibonacci Number

Naive solution

To solve this problem, let’s compute $F_n$ and simply output its last digit:

---

 $FibonacciLastDigit(n)$:
 if $n\leq 1$:
  return $n$
 allocate an array $F[0..n+1]$
 $F[0] \gets 0$
 $F[1] \gets 1$
 for $i$ from $2$ to $n+1$
  $F[i] \gets F[i-1]+F[i-2]$
 return $F[n]$ mod 10

---

Note that Fibonacci numbers grow fast. For example,

$F_{100} = 354224848$ $179261915075.$

Therefore, if we use C++ int 32 or int64_t types for storing $F$, we’ll quickly hit an integer overflow. If we reach out for arbitrary precision numbers, like Java’s BigInteger, or Python’s built-in integers, we’ll notice that the loop runs much slower when the iteration number increases.

Stop and think: The last digit of $F_{102}$ is 6 and the last digit of $F_{103}$ is 7. What is the last digit of $F_{104}$?

It’s not difficult to see that the last digit of $F_{104}$ is equal to 3 and is determined completely by the last digits of $F_{102}$ and $F_{103}$. This suggests a way to make our algorithm more practical. Instead of computing $F_n$ and taking its last digit, we take every intermediate step modulo 10.

Take every intermediate step modulo 10

Here is the main message of this programming challenge: when we need to compute the result of a sequence of arithmetic operations modulo $m$, we take the result of every single operation modulo $m$. This way, we ensure that the numbers we’re working with are small (they fit into standard type in our favorite programming language) and that arithmetic operations are performed quickly on them.

---

 $FibonacciLastDigit(n)$:
 if $n\leq 1$:
  return $n$
 allocate an array $F[0..n+1]$
 $F[0] \gets 0$
 $F[1] \gets 1$
 for $i$ from $2$ to $n+1$
  $F[i] \gets (F[i-1]+F[i-2])$ mod 10
 return $F[n]$

---

Code