🚀 Lucas' Theorem + CRT | O(n log n) | With Resources 🎯
ResourcesLucas' Theorem
Chinese Remainder TheoremIntuitionInstead of simulating the operations until the string length reduces to 2, we can track how often each
# Resources
[Lucas' Theorem](https://en.wikipedia.org/wiki/Lucas%27s_theorem)
[Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Systematic_search)

# Intuition
Instead of simulating the operations until the string length reduces to 2, we can track how often each digit contributes to the final two digits. This contribution follows binomial coefficients.
Thus, the problem reduces to efficiently computing binomial coefficients modulo 10.

Using number theory, we compute $$\binom{n}{k} \mod 10$$ by first calculating $$\binom{n}{k} \mod 2$$ and $$\binom{n}{k} \mod 5$$ separately (since $$2 \times 5 = 10$$) and then combining the results using the Chinese Remainder Theorem.

# Approach
1. Compute $$\binom{n}{k} \bmod 10$$
    - Here, $$n = \text{s.length} - 2$$.
2. Use Lucas’ Theorem to compute $$\binom{n}{k} \bmod p$$
    - This is equivalent to computing $$\binom{n_i}{k_i} \bmod p$$ for each digit in the base $$p$$ representation of $$n$$ and $$k$$.
3. Combine results using the Chinese Remainder Theorem (CRT)
    - Given:
        - $$x \equiv \text{res}_2 \pmod{2}$$
        - $$x \equiv \text{res}_5 \pmod{5}$$
    - We solve for $$x$$ modulo 10.
4. Compute the final two digits
    - Iterate over adjacent pairs in $$s$$ and use the computed coefficients to track their contribution.
    - Compare the resulting first and second digits.

# Complexity
- Time complexity:
Efficiently computed using Lucas’ theorem and CRT, reducing operations to $$O(n \log n)$$

- Space complexity:
$$O(1)$$ as only a few integers are stored

# Code
```cpp []
class Solution {
    int binom10(int n, int k) {
        int res2 = lucas(n, k, 2);
        int res5 = lucas(n, k, 5);
        return chineseRemainder(res2, res5, 2, 5);
    }

    // Naive binomial coefficient
    // https://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula
    int binom(int n, int k) {
        double product = 1;
        for (int i=1; i<=k; i++) {
            product *= 1.0 * (n + 1 - i) / i;
        }
        return (int)product;
    }

    // https://en.wikipedia.org/wiki/Lucas%27s_theorem
    int lucas(int n, int k, int p) {
        int product = 1;
        while (n > 0 || k > 0) {
            int ni = n%p;
            int ki = k%p;

            if (ki > ni) return 0;

            int b = binom(ni, ki);
            product = (product * b) % p;

            n /= p;
            k /= p;
        }
        return product;
    }

    // https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Systematic_search
    int chineseRemainder(int a1, int a2, int n1, int n2) {
        int N = n1*n2;
        for (int x=0; x<N; x++) {
            if (x % n1 == a1 && x % n2 == a2) {
                return x;
            }
        }
        throw "No solution";
    }

public:
    bool hasSameDigits(string s) {
        int n = s.length();
        int l = n-2;
        int a = 0, b = 0;

        for (int i=0; i<n-1; i++) {
            int w = binom10(l, i);

            int d1 = s[i] - '0';
            int d2 = s[i+1] - '0';

            a = (a + w * d1) % 10;
            b = (b + w * d2) % 10;
        }

        return a == b;
    }
};
```
['C++']