3774. Check If Digits Are Equal in String After Operations II
My accepted Python solution to LeetCode problem 3774, Check If Digits Are Equal in String After Operations II, running in 5383ms.
- Difficulty: Hard
- Python
- Runtime 5383ms
- Memory 18.1MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 5383ms, memory 18.1MB, accepted 2025-12-30.
class Solution:
def hasSameDigits(self, s: str) -> bool:
n = len(s)
if n == 2:
return s[0] == s[1]
m = n - 2 # number of operations = n - 2, so we use C(m, i)
# Small factorials for Lucas theorem
fact5 = [1, 1, 2, 6, 24] # 0! to 4! mod 5 = [1,1,2,1,4]
fact5_mod = [1, 1, 2, 1, 4] # actual mod 5 values
# Inverse factorials mod 5
inv_fact5 = [1, 1, 3, 2, 4] # computed: inv(1)=1, inv(1)=1, inv(2)=3, inv(1)=1, inv(4)=4
def C_mod5_small(n, k):
if k > n or k < 0 or n < 0:
return 0
if n >= 5:
return 0 # Should not happen in Lucas
# C(n, k) = n! / (k! * (n-k)!)
# Direct computation for small values
pascal = [
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1]
]
return pascal[n][k] % 5
def C_mod5(n, k):
if k > n or k < 0:
return 0
result = 1
while n > 0 or k > 0:
ni = n % 5
ki = k % 5
if ki > ni:
return 0
result = (result * C_mod5_small(ni, ki)) % 5
n //= 5
k //= 5
return result
def C_mod2(n, k):
if k > n or k < 0:
return 0
# C(n, k) mod 2 = 1 if (k & ~n) == 0, else 0
# This means: all bits set in k must also be set in n
return 1 if (k & ~n) == 0 else 0
def compute_digit(start):
result_mod2 = 0
result_mod5 = 0
for i in range(m + 1):
digit_val = int(s[start + i])
c2 = C_mod2(m, i)
c5 = C_mod5(m, i)
result_mod2 = (result_mod2 + c2 * digit_val) % 2
result_mod5 = (result_mod5 + c5 * digit_val) % 5
# CRT to combine mod 2 and mod 5 to get mod 10
for x in range(10):
if x % 2 == result_mod2 and x % 5 == result_mod5:
return x
return 0
d0 = compute_digit(0)
d1 = compute_digit(1)
return d0 == d1