Solution You are Looking For
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```python3 []
from typing import List

# Precomputed small binomials mod 5 for n < 5:
_small = {
    0: [1],
    1: [1, 1],
    2: [1, 2, 1],
    3: [1, 3, 3, 1],
    4: [1, 4, 1, 4, 1]
}

def nCr_mod2(n: int, r: int) -> int:
    """Compute C(n, r) mod 2 using Lucas theorem for mod 2."""
    if r > n:
        return 0
    # In mod 2, C(n, r) = 1 if and only if r's binary representation is a subset of n's.
    while n or r:
        if (r & 1) > (n & 1):
            return 0
        n //= 2
        r //= 2
    return 1

def nCr_mod5(n: int, r: int) -> int:
    """Compute C(n, r) mod 5 using Lucas theorem."""
    if r > n:
        return 0
    if n < 5:
        return _small[n][r]
    n0, r0 = n % 5, r % 5
    # If r0 > n0, then the small binom is 0.
    if r0 > n0:
        return 0
    return (_small[n0][r0] * nCr_mod5(n // 5, r // 5)) % 5

def nCr_mod10(n: int, r: int) -> int:
    """Combine results mod 2 and mod 5 using CRT to get binom(n, r) mod 10."""
    a = nCr_mod2(n, r)  # mod 2 result
    b = nCr_mod5(n, r)  # mod 5 result
    # We need x mod 10 such that:
    #   x ≡ a (mod 2) and x ≡ b (mod 5)
    # The possibilities for x given b are b and b+5.
    for candidate in (b, b + 5):
        if candidate % 2 == a:
            return candidate % 10
    return 0  # fallback; though one candidate must work.

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        n = len(s)
        # Convert string to list of integers.
        digits = [int(ch) for ch in s]
        # Number of operations = n - 2, so we need row r = n - 2 of Pascal's triangle.
        r = n - 2
        F0, F1 = 0, 0
        # Iterate j from 0 to r (inclusive).
        for j in range(r + 1):
            coef = nCr_mod10(r, j)
            F0 = (F0 + coef * digits[j]) % 10
            F1 = (F1 + coef * digits[j + 1]) % 10
        return F0 == F1

# Example usage:
# if __name__ == "__main__":
#     sol = Solution()
#     # Provided test cases:
#     print("s = '3902' ->", sol.hasSameDigits("3902"))   # Expected True
#     print("s = '34789' ->", sol.hasSameDigits("34789"))  # Expected False
#     # The problematic test case:
#     print("s = '8506969' ->", sol.hasSameDigits("8506969"))  # Expected True

```
['Python3']