Explanation with Lucas Theorem and Chinese remainder theorem - O(n log n)
IntuitionYou need to have an understanding of pascals triangle, lucas theorem and chinese remainder thm.Now, if you do the steps of forming the two digits strin
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
You need to have an understanding of pascals triangle, lucas theorem and chinese remainder thm.

Now, if you do the steps of forming the two digits string, you'll see pascal triangle
![image.png](https://assets.leetcode.com/users/images/4a4bc279-ab00-469b-87bb-3862e115fe22_1740917495.638942.png)

now, as per lucas thm, you can calculate nck mod p (binomial coefficient of n the row and kth column in pascal triagnle).
If you select p as 2 and 5.
Then with Chinese Thm you can calculate mod 10 using the formula which I used.
```
X = (a1*M1*InvM1 + a2*M2*InvM2) mod M
m1 = 2, m2 = 5, M = m1*m2
a1 = nck mod 2, a2 = nck mod 5
M1 = M/m1, M2 = M/m2
M1 * InvM1 ≅ 1 (mod m1)
M2 * InvM2 ≅ 1 (mod m2)
```


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

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

# Code
```java []
class Solution {
    double[] fact = {1, 1, 2, 6, 24};

    public boolean hasSameDigits(String s) {
        return CheckLastTwoDigitsAreEqual(s, s.length());        
    }
    
    public boolean CheckLastTwoDigitsAreEqual(String s, int n){
        int i, val1 = 0, val2 = 0;
        for(i=0; i<n-1; i++){
            int coeff = findMod10(n-2, i);
            val1 = (val1%10+((s.charAt(i)-'0')%10*coeff)%10)%10;
            val2 = (val2%10+((s.charAt(i+1)-'0')%10*coeff)%10)%10;
        }
        return val1 == val2;
    }
    public int findMod10(int n, int k){
        // to find Mod 10, apply chinese remainder theorem with p1 = 2 and p2 = 5
        int a1 = lucasTheorem(n, k, 2);
        int a2 = lucasTheorem(n, k, 5);

        int M1 = 5, M2 = 2; 
        // calculate multiplicative inverse of M1 and M2
        int invM1 = findInv(M1, 2), invM2 = findInv(M2, 5);
        return (a1*M1*invM1+a2*M2*invM2)%10;

        
    }
    public int findInv(int a, int b){
        // Since M1 = 2 and M2 = 5 always, we can directly return the
        // multiplicative inverse
        return b == 2 ? 1 : 3; 
    }
    public int lucasTheorem(int d, int k, int num){
        // lucasTheorem
        int a, b;
        double prod = 1;

        while(d != 0 || k != 0){
            if (d == 0){
                b = k%num;
                if (b != 0){
                    return 0;
                }
            }
            else if (k != 0){
                a = d%num;
                b = k%num;
                if (b > a){
                    return 0;
                }
                prod *= fact[a]/(fact[b]*fact[a-b]);
            }
            d /= num;
            k /=num;
        }
        return (int)prod;
        
    }
}
```
['Java']