🔥 Efficient Solution Using Pascal's Triangle, Lucas' Theorem & CRT
IntuitionAfter Getting Tle   haam saab 😭😭Here's the observation:The final two digits are determined by a pattern of additions that follows Pascal's Triangle.Eac
# Intuition
**After Getting Tle   haam saab 😭😭**
Here's the observation:
The final two digits are determined by a pattern of additions that follows Pascal's Triangle.
Each digit's contribution to the result can be represented by binomial coefficients.
Instead of running the entire transformation, we can directly compute the two final digits using properties of modular arithmetic and binomial coefficients.
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
![Screenshot 2025-02-23 235718.png](https://assets.leetcode.com/users/images/e6dfe811-129f-4a90-bd94-33c834c765d1_1740335277.5825462.png)

![Screenshot 2025-02-23 235732.png](https://assets.leetcode.com/users/images/3ee6a1df-d9db-47b8-8e0d-6bd89510a85b_1740335296.22236.png)






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

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

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

# Code
```cpp []


class Solution {
public:
    int nCrModP(int n, int r, int p) {
        if (r == 0) return 1;
        int ni = n % p, ri = r % p;
        return (nCrModP(n / p, r / p, p) * nCrSmall(ni, ri, p)) % p;
    }


    int nCrSmall(int n, int r, int p) {
        if (r > n) return 0;
        if (r == 0 || r == n) return 1;

        int res = 1;
        for (int i = 0; i < r; i++) {
            res = res * (n - i) % p;
            res = res * modInverse(i + 1, p) % p;
        }
        return res;
    }

    int modInverse(int a, int p) {
        int res = 1;
        int power = p - 2;
        while (power) {
            if (power % 2) res = (res * a) % p;
            a = (a * a) % p;
            power /= 2;
        }
        return res;
    }

    int crt(int a, int b) {
        for (int i = 0; i < 10; i++) {
            if (i % 2 == a && i % 5 == b) {
                return i;
            }
        }
        return 0; 
    }

    bool hasSameDigits(string s) {
        int n = s.length();
        if (n == 2) return s[0] == s[1];

        int d1 = 0, d2 = 0;

        for (int i = 0; i < n - 1; i++) {
            int coef = crt(nCrModP(n - 2, i, 2), nCrModP(n - 2, i, 5));
            d1 = (d1 + (s[i] - '0') * coef) % 10;
        }
        for (int i = 1; i < n; i++) {
            int coef = crt(nCrModP(n - 2, i - 1, 2), nCrModP(n - 2, i - 1, 5));
            d2 = (d2 + (s[i] - '0') * coef) % 10;
        }

        return d1 == d2;
    }
};

```
['Math', 'Combinatorics', 'C++']