You are given a string s consisting of digits. Perform the following operation repeatedly until the string has exactly two digits:
- For each pair of consecutive digits in
s, starting from the first digit, calculate a new digit as the sum of the two digits modulo 10. - Replace
swith the sequence of newly calculated digits, maintaining the order in which they are computed.
Return true if the final two digits in s are the same; otherwise, return false.
Example 1:
Input: s = “3902”
Output: true
Explanation:
- Initially,
s = "3902" - First operation:
(s[0] + s[1]) % 10 = (3 + 9) % 10 = 2(s[1] + s[2]) % 10 = (9 + 0) % 10 = 9(s[2] + s[3]) % 10 = (0 + 2) % 10 = 2sbecomes"292"
- Second operation:
(s[0] + s[1]) % 10 = (2 + 9) % 10 = 1(s[1] + s[2]) % 10 = (9 + 2) % 10 = 1sbecomes"11"
- Since the digits in
"11"are the same, the output istrue.
Example 2:
Input: s = “34789”
Output: false
Explanation:
- Initially,
s = "34789". - After the first operation,
s = "7157". - After the second operation,
s = "862". - After the third operation,
s = "48". - Since
'4' != '8', the output isfalse.
Constraints:
3 <= s.length <= 105sconsists of only digits.
from typing import List
class Solution:
def binmod10(self, n: int, k: int) -> int:
mod2 = self.binmod2(n, k)
mod5 = self.binmod5(n, k)
for i in range(10):
if i % 2 == mod2 and i % 5 == mod5:
return i
return 0
def binmod2(self, n: int, k: int) -> int:
# Compute binom(n, k) mod 2 using bit-by-bit checking.
while k > 0:
if (k & 1) > (n & 1):
return 0
n >>= 1
k >>= 1
return 1
def binmod5(self, n: int, k: int) -> int:
# Compute binom(n, k) mod 5 by processing each digit in base 5.
res = 1
while n > 0 or k > 0:
nd = n % 5
kd = k % 5
if kd > nd:
return 0
res = (res * self.binsmall(nd, kd)) % 5
n //= 5
k //= 5
return res
def binsmall(self, n: int, k: int) -> int:
# For n, k less than 5, use precomputed factorials modulo 5.
if k > n:
return 0
fact = [1, 1, 2, 1, 4] # factorials mod 5 for 0, 1, 2, 3, 4.
numerator = fact[n]
denominator = (fact[k] * fact[n - k]) % 5
deninv = 0
# Find the multiplicative inverse of denominator modulo 5.
for i in range(5):
if (denominator * i) % 5 == 1:
deninv = i
break
return (numerator * deninv) % 5
def hasSameDigits(self, s: str) -> bool:
"""
For a string s, let L = len(s) and m = L - 2.
For each i in [0, m], compute:
val = binmod10(m, i)
s1 += val * (digit at position i) mod 10
s2 += val * (digit at position i+1) mod 10
Return True if s1 and s2 (mod 10) are equal.
"""
L = len(s)
m = L - 2
s1, s2 = 0, 0
for i in range(m + 1):
val = self.binmod10(m, i)
d1 = int(s[i])
d2 = int(s[i+1])
s1 = (s1 + val * d1) % 10
s2 = (s2 + val * d2) % 10
return s1 == s2