Problem

Given two integers m and n with 0 ≤ m ≤ n, compute the last digit (units digit) of the partial sum

1

F(m) + F(m+1) + ... + F(n)
  • Input: integers m and n (either as integers or as decimal strings for very large values).
  • Output: S = (F(m) + ... + F(n)) mod 10 (a single digit 0–9).

Examples

Example 1

1
2
3

Input: m = 3, n = 7
Output: 1
Explanation: F3+F4+F5+F6+F7 = 2+3+5+8+13 = 31 -> last digit 1

Example 2

1
2

Input: m = 10, n = 2000000000000
Output: (computed via Pisano reduction)

Solution

Key identity: the partial sum has a closed form

1

S(m,n) = F(m) + ... + F(n) = F(n+2) − F(m+1)

Therefore it suffices to compute F(n+2) mod 10 and F(m+1) mod 10, subtract them modulo 10, and return a non-negative digit.

Because F(k) mod 10 is periodic with Pisano period 60, reduce indices modulo 60 before evaluating. Two practical methods follow.

Method 1 — Pisano reduction + iterative Fibonacci (recommended)

Intuition

Reduce the large indices n+2 and m+1 modulo 60 (Pisano period for modulus 10). Then compute the two Fibonacci values by iterating at most 60 steps.

Approach

  • Compute a = (n+2) % 60 and b = (m+1) % 60. If n or m are given as decimal strings, reduce them digit-by-digit: r = (r*10 + d) % 60.
  • Compute F(a) mod 10 and F(b) mod 10 by iterating up to 60 steps with x,y = y, (x+y) % 10.
  • Return (F(a) - F(b) + 10) % 10 to avoid negative digits.

Edge cases:

  • If m > n treat as invalid; if m == n the result is F(n) % 10.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
 public:
  static int reduce_mod60_str(const std::string &s) {
    int r = 0; for (char ch : s) r = (r*10 + (ch - '0')) % 60; return r;
  }

  static int fib_mod10_by_idx(int k) {
    int a = 0, b = 1;
    for (int i = 0; i < k; ++i) { int nxt = (a + b) % 10; a = b; b = nxt; }
    return a;
  }

  int partial_sum_last_digit_str(const std::string &ms, const std::string &ns) {
    int m = reduce_mod60_str(ms); int n = reduce_mod60_str(ns);
    int a = (n + 2) % 60; int b = (m + 1) % 60;
    int fa = fib_mod10_by_idx(a); int fb = fib_mod10_by_idx(b);
    return (fa - fb + 10) % 10;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

package main

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

func PartialSumLastDigitStr(ms, ns string) int {
  m := reduceMod60Str(ms); n := reduceMod60Str(ns)
  a := (n+2)%60; b := (m+1)%60
  fa := fibMod10ByIdx(a); fb := fibMod10ByIdx(b)
  return (fa - fb + 10) % 10
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  private static int reduceMod60Str(String s) {
    int r = 0; for (char ch : s.toCharArray()) r = (r*10 + (ch - '0')) % 60; return r;
  }
  private static int fibMod10ByIdx(int k) {
    int a = 0, b = 1; for (int i=0;i<k;++i) { int nxt=(a+b)%10; a=b; b=nxt; } return a;
  }
  public int partialSumLastDigitStr(String ms, String ns) {
    int m = reduceMod60Str(ms), n = reduceMod60Str(ns);
    int a = (n + 2) % 60, b = (m + 1) % 60;
    int fa = fibMod10ByIdx(a), fb = fibMod10ByIdx(b);
    return (fa - fb + 10) % 10;
  }
}
1
2
3
4
5
6
7
8
9

object Solution {
  private fun reduceMod60Str(s: String): Int { var r=0; for (ch in s) r=(r*10 + (ch - '0')) % 60; return r }
  private fun fibMod10ByIdx(k: Int): Int { var a=0; var b=1; repeat(k) { val nxt=(a+b)%10; a=b; b=nxt }; return a }
  fun partialSumLastDigitStr(ms: String, ns: String): Int {
    val m = reduceMod60Str(ms); val n = reduceMod60Str(ns)
    val a = (n + 2) % 60; val b = (m + 1) % 60
    return (fibMod10ByIdx(a) - fibMod10ByIdx(b) + 10) % 10
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    @staticmethod
    def reduce_mod60_str(s: str) -> int:
        r = 0
        for ch in s:
            r = (r*10 + (ord(ch) - 48)) % 60
        return r

    @staticmethod
    def fib_mod10_by_idx(k: int) -> int:
        a, b = 0, 1
        for _ in range(k):
            a, b = b, (a + b) % 10
        return a

    def partial_sum_last_digit_str(self, ms: str, ns: str) -> int:
        m = self.reduce_mod60_str(ms); n = self.reduce_mod60_str(ns)
        a = (n + 2) % 60; b = (m + 1) % 60
        return (self.fib_mod10_by_idx(a) - self.fib_mod10_by_idx(b) + 10) % 10

    def partial_sum_last_digit(self, m: int, n: int) -> int:
        return self.partial_sum_last_digit_str(str(m), str(n))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

pub struct Solution;
impl Solution {
  fn reduce_mod60_str(s: &str) -> usize { s.bytes().fold(0usize, |r,ch| (r*10 + (ch - b'0') as usize) % 60) }
  fn fib_mod10_by_idx(k: usize) -> u8 { let (mut a, mut b) = (0u8, 1u8); for _ in 0..k { let nxt = (a + b) % 10; a = b; b = nxt; } a }
  pub fn partial_sum_last_digit_str(ms: &str, ns: &str) -> u8 {
    let m = Self::reduce_mod60_str(ms); let n = Self::reduce_mod60_str(ns);
    let a = (n + 2) % 60; let b = (m + 1) % 60;
    ((Self::fib_mod10_by_idx(a) + 10) - Self::fib_mod10_by_idx(b)) % 10
  }
}

Complexity

  • ⏰ Time complexity: O(L + P) where L is the length (in digits) of m and n when given as strings and P = 60 (Pisano period for mod 10). Reduction takes O(L) and the iterative Fibonacci steps take at most O(60).
  • 🧺 Space complexity: O(1) extra space.

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

Intuition

After reducing indices to k1=(n+2)%60 and k2=(m+1)%60, fast-doubling computes F(k) mod 10 in O(log k) steps. For mod 10 the k are ≤ 60 so this is optional.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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)

# reduce indices then return (fib_pair(k1,10)[0] - fib_pair(k2,10)[0] + 10) % 10

Complexity

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