Problem

Given an integer n (possibly very large), return the last digit (units digit) of the n-th Fibonacci number F(n).

  • Input: integer n (may be provided as a large integer or as a decimal string).
  • Output: single digit F(n) mod 10.

Examples

Example 1

1
2

Input: n = 0
Output: 0

Example 2

1
2

Input: n = 2
Output: 1

Example 3

1
2

Input: n = 7
Output: 3

Solution

Three straightforward approaches are useful here:

  • Method 1 — naive Fibonacci (for completeness)
  • Method 2 — iterative computation with modulus 10 (O(n) time, O(1) space)
  • Method 3 — exploit cyclicity (Pisano period for modulus 10 is 60) to get an O(1) answer after precomputation

Method 1 — Naive Fibonacci

Intuition

Compute F(n) directly and take its last digit. This is straightforward but impractical for large n because Fibonacci numbers grow exponentially.

Approach

  • Use two variables a and b to iteratively build Fibonacci numbers up to n and return F(n) % 10.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
 public:
  long long fib_naive(unsigned long long n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    long long a = 0, b = 1;
    for (unsigned long long i = 2; i <= n; ++i) {
      long long nxt = a + b; a = b; b = nxt;
    }
    return b;
  }
};

Complexity

  • ⏰ Time complexity: O(n) to compute F(n) by iteration.
  • 🧺 Space complexity: O(1) extra space.

Method 2 — Iterative modulo 10

Intuition

We only need the last digit, so compute Fibonacci terms modulo 10 during iteration; arithmetic stays small and safe.

Approach

  • Maintain a = 0, b = 1 and iterate n times updating a, b = b, (a+b) % 10.
  • If n is provided as a decimal string, compute n % k (for k = cycle length if used) as needed; otherwise iterate n steps.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class SolutionMod {
 public:
  int last_digit(unsigned long long n) {
    int a = 0, b = 1;
    if (n == 0) return 0;
    for (unsigned long long i = 1; i <= n; ++i) {
      int nxt = (a + b) % 10; a = b; b = nxt;
    }
    return a % 10;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

package main

func LastDigitFib(n uint64) int {
  a, b := 0, 1
  if n == 0 { return 0 }
  for i := uint64(1); i <= n; i++ {
    a, b = b, (a+b) % 10
  }
  return a % 10
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
  public int lastDigit(long n) {
    int a = 0, b = 1;
    if (n == 0) return 0;
    for (long i = 1; i <= n; ++i) {
      int nxt = (a + b) % 10; a = b; b = nxt;
    }
    return a % 10;
  }
}
1
2
3
4
5
6
7
8

class Solution {
  fun lastDigit(n: Long): Int {
    var a = 0; var b = 1
    if (n == 0L) return 0
    for (i in 1..n) { val nxt = (a + b) % 10; a = b; b = nxt }
    return a % 10
  }
}
1
2
3
4
5
6
7
8

class Solution:
    def last_digit(self, n: int) -> int:
        a, b = 0, 1
        if n == 0:
            return 0
        for _ in range(1, n + 1):
            a, b = b, (a + b) % 10
        return a % 10
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

pub struct Solution;
impl Solution {
  pub fn last_digit(mut n: u128) -> u8 {
    if n == 0 { return 0 }
    let (mut a, mut b) = (0u8, 1u8);
    for _ in 1..=n {
      let nxt = (a + b) % 10; a = b; b = nxt;
    }
    a
  }
}

Complexity

  • ⏰ Time complexity: O(n) — performs n iterations.
  • 🧺 Space complexity: O(1) extra space.

Method 3 — Precompute cycle (Pisano period for modulus 10)

Intuition

For modulus 10 the Pisano period is 60: the sequence of last digits repeats every 60 terms. So F(n) mod 10 = F(n % 60) mod 10. Precompute the first 60 last digits and answer any query in O(1).

Approach

  1. Precompute array cycle[0..59] with cycle[i] = F(i) mod 10.
  2. Compute idx = n % 60 (if n is a decimal string compute idx by streaming digits: idx = (idx*10 + d) % 60).
  3. Return cycle[idx].

Edge cases:

  • n == 0 -> 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class SolutionPisano {
 public:
  int last_digit(unsigned long long n) {
    static int cycle[60] = {0};
    static bool init = false;
    if (!init) {
      init = true; cycle[0] = 0; cycle[1] = 1;
      for (int i = 2; i < 60; ++i) cycle[i] = (cycle[i-1] + cycle[i-2]) % 10;
    }
    return cycle[n % 60];
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

package main

var pisano60 = func() [60]int {
  var c [60]int
  c[0], c[1] = 0, 1
  for i := 2; i < 60; i++ { c[i] = (c[i-1] + c[i-2]) % 10 }
  return c
}()

func LastDigitFibPisano(n uint64) int { return pisano60[n % 60] }
1
2
3
4
5
6
7
8
9

class Solution {
  private static final int[] CYCLE = new int[60];
  static {
    CYCLE[0] = 0; CYCLE[1] = 1;
    for (int i = 2; i < 60; ++i) CYCLE[i] = (CYCLE[i-1] + CYCLE[i-2]) % 10;
  }

  public int lastDigit(long n) { return CYCLE[(int)(n % 60)]; }
}
1
2
3
4

object Solution {
  private val CYCLE = IntArray(60).also { it[0]=0; it[1]=1; for (i in 2..59) it[i]=(it[i-1]+it[i-2])%10 }
  fun lastDigit(n: Long) = CYCLE[(n % 60).toInt()]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    CYCLE = [0,1] + [0]*58
    for i in range(2,60):
        CYCLE[i] = (CYCLE[i-1] + CYCLE[i-2]) % 10

    def last_digit(self, n: int) -> int:
        return Solution.CYCLE[n % 60]

    def last_digit_str(self, s: str) -> int:
        r = 0
        for ch in s:
            r = (r*10 + (ord(ch)-48)) % 60
        return Solution.CYCLE[r]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

pub struct Solution;
impl Solution {
  fn pisano60() -> [u8;60] {
    let mut c = [0u8;60]; c[0]=0; c[1]=1;
    for i in 2..60 { c[i] = (c[i-1] + c[i-2]) % 10 }
    c
  }

  pub fn last_digit(n: u128) -> u8 { let c = Self::pisano60(); c[(n % 60) as usize] }
}

Complexity

  • ⏰ Time complexity: O(1) after precomputation (precompute cost O(60) negligible). Overall per-query time O(1).
  • 🧺 Space complexity: O(1) extra space for the 60-entry cycle.