Last digit of a sum of the first n Fibonacci numbers

Problem

Given an integer n, compute the last digit of the sum

F(0) + F(1) + ... + F(n)

Return S(n) mod 10 (the units digit). n can be large (possibly given as a decimal string).

Examples

Example 1

Input: n = 3
Output: 4
Explanation: F0+F1+F2+F3 = 0+1+1+2 = 4

Example 2

Input: n = 1000000000000
Output: ? (computed via Pisano reduction)

Solution

Key identity: S(n) = F(0)+...+F(n) = F(n+2) − 1. So the problem reduces to computing F(n+2) mod 10 and subtracting 1 (mod 10).

Method 1 — Pisano reduction + iterative Fibonacci

Intuition

For modulus 10 the Pisano period P is 60, so F(n+2) mod 10 = F((n+2) % 60) mod 10. Reducing the index to k = (n+2) % 60 makes the value easy to compute by simple iteration.

Approach

• Compute k = (n+2) % 60. If n is given as a decimal string, compute k by streaming digits: k = (k*10 + d) % 60 for each digit d.
• Compute F(k) mod 10 by iterating k steps with a,b = b, (a+b)%10.
• Return (F(k) - 1 + 10) % 10 to ensure a non-negative result.

Edge cases:

• If n < 0 treat as invalid.
• If n is small the reduction still works.

Code

C++

class Solution {
 public:
  int sum_last_digit_str(const std::string &s) {
    // reduce n modulo 60
    int k = 0;
    for (char ch : s) { k = (k*10 + (ch - '0')) % 60; }
    k = (k + 2) % 60; // n+2
    int a = 0, b = 1;
    for (int i = 0; i < k; ++i) { int nxt = (a + b) % 10; a = b; b = nxt; }
    int res = (a - 1 + 10) % 10;
    return res;
  }
};

Go

package main

func SumLastDigitStr(s string) int {
  k := 0
  for _, ch := range s { k = (k*10 + int(ch-'0')) % 60 }
  k = (k + 2) % 60
  a, b := 0, 1
  for i := 0; i < k; i++ { a, b = b, (a+b)%10 }
  return (a-1+10)%10
}

Java

class Solution {
  public int sumLastDigitStr(String s) {
    int k = 0;
    for (char ch : s.toCharArray()) { k = (k*10 + (ch - '0')) % 60; }
    k = (k + 2) % 60;
    int a = 0, b = 1;
    for (int i = 0; i < k; ++i) { int nxt = (a + b) % 10; a = b; b = nxt; }
    return (a - 1 + 10) % 10;
  }
}

Kotlin

object Solution {
  fun sumLastDigitStr(s: String): Int {
    var k = 0
    for (ch in s) k = (k*10 + (ch - '0')) % 60
    k = (k + 2) % 60
    var a = 0; var b = 1
    repeat(k) { val nxt = (a + b) % 10; a = b; b = nxt }
    return (a - 1 + 10) % 10
  }
}

Python

class Solution:
    def sum_last_digit_str(self, s: str) -> int:
        k = 0
        for ch in s:
            k = (k*10 + (ord(ch) - 48)) % 60
        k = (k + 2) % 60
        a, b = 0, 1
        for _ in range(k):
            a, b = b, (a + b) % 10
        return (a - 1 + 10) % 10

    def sum_last_digit(self, n: int) -> int:
        return self.sum_last_digit_str(str(n))

Rust

pub struct Solution;
impl Solution {
  pub fn sum_last_digit_str(s: &str) -> u8 {
    let mut k: usize = 0;
    for ch in s.bytes() { k = (k*10 + (ch - b'0') as usize) % 60; }
    k = (k + 2) % 60;
    let (mut a, mut b) = (0u8, 1u8);
    for _ in 0..k { let nxt = (a + b) % 10; a = b; b = nxt; }
    ((a + 9) % 10)
  }
}

Complexity

• ⏰ Time complexity: O(L + P) where L is length of decimal n (to reduce mod 60) and P=60 for the iteration; overall O(L + 60) -> O(L) for large-string n.
• 🧺 Space complexity: O(1) extra space.

Method 2 — Pisano reduction + fast-doubling (optional)

Intuition

After reducing the index to k = (n+2) % 60, computing F(k) can be done with fast-doubling in O(log k); since k ≤ 60 this is tiny, but fast-doubling is useful if modulus or period were larger.

Code (Python fast-doubling sketch)

def fib_pair(n: int, mod: int):
    if n == 0: return (0,1)
    a,b = fib_pair(n>>1, mod)
    c = (a * ((2*b - a) % mod)) % mod
    d = ((a*a) % mod + (b*b) % mod) % mod
    if n & 1:
        return (d, (c+d) % mod)
    else:
        return (c, d)

def sum_last_digit_fast(n_str: str) -> int:
    # reduce and compute
    k = 0
    for ch in n_str: k = (k*10 + (ord(ch)-48)) % 60
    k = (k+2) % 60
    return (fib_pair(k, 10)[0] - 1 + 10) % 10

Complexity

• ⏰ Time complexity: O(L + log P) where L is digits of n and P=60.
• 🧺 Space complexity: O(log P) recursion depth (or O(1) iterative).