Java Beats 94% (pascal triangle + CRT)
IntuitionCompute last row of Pascals triangle and add accordingly.ApproachCompute last row mod 5 and mod 2 (since we can divide in Z5​,Z2​ this case so we can d
# Intuition
Compute last row of Pascals triangle and add accordingly.

# Approach
Compute last row mod 5 and mod 2 (since we can divide in $Z_5,Z_2$ this case so we can do it $O(nlog(n))$ and use CRT do find the results $\mod 10$

# Complexity
- Time complexity:
$O(nlog(n))$

- Space complexity:
$O(n)$

# Code
```java []
import java.math.BigInteger;

class Solution {
    public boolean hasSameDigits(String s) {
        int n = s.length();
        int[] mod5 = new int[n - 1]; // mod[i] = i choose (n - 1) mod 5
        int[] fac2 = new int[n  -1]; // counts 2 factors (we only need to check divisibility)
        int[] fac5 = new int[n - 1]; // counts 5 factor

        int[] inverse5 = {0, 1, 3, 2, 4};
        fac2[0] = 0;
        fac2[n - 2] = 0;

        mod5[0] = 1;
        mod5[n  - 2] = 1;

        fac5[0] = 0;
        fac5[n -2] = 0;

        for(int i = 1; i <= n - 3; i++){
            // Track factors mod 2 
            Pair a_2  = factors(i, 2); // divisor
            Pair a_5 = factors(i,5); // divisor

            Pair b_2 = factors(n  -i - 1, 2);
            Pair b_5 = factors(n  - i - 1, 5);

            fac2[i] = fac2[i - 1] + b_2.count - a_2.count;
            fac5[i] = fac5[i - 1] + b_5.count - a_5.count;

            mod5[i] = mod5[i - 1]*b_5.modulo*inverse5[a_5.modulo] %5;
        }

        int[] arr = new int[n - 1];
        for(int i = 0; i < n - 1; i++){
            int m5 = fac5[i] != 0 ? 0 : mod5[i];
            int m2 = fac2[i] != 0 ? 0 : 1;
            arr[i] = m5 % 2 == m2 ? m5 : m5 + 5;
            
        }


        int a = 0;
        int b = 0;
        for(int i = 0; i < n -1; i++){

            a += (arr[i]*((int) s.charAt(i)))%10;
            b += (arr[i]*((int) s.charAt(i+1)))%10;
        }

        return (a%10) == (b%10);
    }

    public Pair factors(int n, int div){
        Pair res = new Pair(0,0);
        while(n % div == 0){
            n /= div;
            res.count++;
        }
        res.modulo = n % div;

        return res;
    }

}


class Pair {
    int count;
    int modulo;

    Pair(int cnt, int mod){
        count = cnt;
        modulo = mod;
    }
}
```
['Java']