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

[{"language":"C++","code":"class Solution {\n public:\n  int sum_last_digit_str(const std::string &s) {\n    // reduce n modulo 60\n    int k = 0;\n    for (char ch : s) { k = (k*10 + (ch - '0')) % 60; }\n    k = (k + 2) % 60; // n+2\n    int a = 0, b = 1;\n    for (int i = 0; i < k; ++i) { int nxt = (a + b) % 10; a = b; b = nxt; }\n    int res = (a - 1 + 10) % 10;\n    return res;\n  }\n};","lang":"cpp"},{"language":"Go","code":"package main\n\nfunc SumLastDigitStr(s string) int {\n  k := 0\n  for _, ch := range s { k = (k*10 + int(ch-'0')) % 60 }\n  k = (k + 2) % 60\n  a, b := 0, 1\n  for i := 0; i < k; i++ { a, b = b, (a+b)%10 }\n  return (a-1+10)%10\n}","lang":"go"},{"language":"Java","code":"class Solution {\n  public int sumLastDigitStr(String s) {\n    int k = 0;\n    for (char ch : s.toCharArray()) { k = (k*10 + (ch - '0')) % 60; }\n    k = (k + 2) % 60;\n    int a = 0, b = 1;\n    for (int i = 0; i < k; ++i) { int nxt = (a + b) % 10; a = b; b = nxt; }\n    return (a - 1 + 10) % 10;\n  }\n}","lang":"java"},{"language":"Kotlin","code":"object Solution {\n  fun sumLastDigitStr(s: String): Int {\n    var k = 0\n    for (ch in s) k = (k*10 + (ch - '0')) % 60\n    k = (k + 2) % 60\n    var a = 0; var b = 1\n    repeat(k) { val nxt = (a + b) % 10; a = b; b = nxt }\n    return (a - 1 + 10) % 10\n  }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def sum_last_digit_str(self, s: str) -> int:\n        k = 0\n        for ch in s:\n            k = (k*10 + (ord(ch) - 48)) % 60\n        k = (k + 2) % 60\n        a, b = 0, 1\n        for _ in range(k):\n            a, b = b, (a + b) % 10\n        return (a - 1 + 10) % 10\n\n    def sum_last_digit(self, n: int) -> int:\n        return self.sum_last_digit_str(str(n))","lang":"python"},{"language":"Rust","code":"pub struct Solution;\nimpl Solution {\n  pub fn sum_last_digit_str(s: &str) -> u8 {\n    let mut k: usize = 0;\n    for ch in s.bytes() { k = (k*10 + (ch - b'0') as usize) % 60; }\n    k = (k + 2) % 60;\n    let (mut a, mut b) = (0u8, 1u8);\n    for _ in 0..k { let nxt = (a + b) % 10; a = b; b = nxt; }\n    ((a + 9) % 10)\n  }\n}","lang":"rust"}]

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).

8:["$","div",null,{"className":"max-w-7xl mx-auto px-4 py-8"

Related Tags