Java most detailed and beginner friendly solution with proper explanation for each step.
IntuitionThe intution for this problem comes from observing the patterns, let's see few examples:
Eg: 2 digits (a b)The final 2 digits are a%10 & b%10
Eg: 3 dig
# Intuition
The intution for this problem comes from observing the patterns, let's see few examples:
**Eg: 2 digits (a b)**
The final 2 digits are a%10 & b%10
**Eg: 3 digits (a b c)**
Final ans: (a+b)%10 & (b+c)%10
**Eg: 4 digits (a b c d)**
Final ans: (a+2b+c)%10 & (b+2c+d)%10
**Eg: 5 digits (a b c d e)**
Final ans: (a+3b+3c+d)%10 & (b+3c+3d+e)%10
**Eg: 6 digits (a b c d e f)**
Final ans: (a+4b+6c+4d+e)%10 & (b+4c+6d+4e+f)%10

If we see the ans can be computed quickly if we can find out the coefficient at every step and if we closely look these coefficients are binomial coefficients mod 10 which is (n-2)Ck mod 10.

**Eg: 6 digits**
n = 6, n-2 = 4
0th coefficient => k=0 => 4C0 mod 10 -> 1
1st coefficient => k=1 => 4C1 mod 10 -> 4
2nd coefficient => k=2 => 4C2 mod 10 -> 6
and so on...

To efficiently calculate these coefficients we make use of Lucas algorithm and Chinese Reminder Theorem.

# Approach
**Lucas algorithm:**
![image.png](https://assets.leetcode.com/users/images/f48cca4b-591c-4c49-8bb2-71f66d623610_1740297742.133564.png)

Since we see that for lucas algorithm p must be a prime so we break 10 into 2 primes 2 and 5 and find the binomial coefficient for 2 and 5.

**Let's take an example of 2:
n=6, k=3, p=2**
n=6, in base 2 -> 110 -> 1 * 2^2 + 1 * 2^1 + 0 * 2^0 = 6
k=3, in base 2 -> 011 -> 0 * 2^2 + 1 * 2^1 + 1 * 2^0 = 3

Now we need to take digits at every position in both n & k and do (niCki) mod p.

Now using Lucas algorithm, 6C3 mod 2 is ((1C0 mod 2) * (1C1 mod 2) * (0C1 mod 2)) mod 2.

**Important point to note is if for any digit k>n, then the entire product becomes 0, since there is no way to choose more k from less n. i.e. 
if k > n then answer is 0**

**Hence we see if the n&k is equal to k that means all the digits in k should have only 1s where n also has 1s if not at that point k>n and hence product is zero.**

**So for 2 -> n&k==k then answer is 1 or it's 0.**

**For 5 for the same example:
n=6, k=3, p=2**
n=6 in base 5 -> 11 -> 1 * 5^1 + 1 * 5^0 = 6
k=3 in base 5 -> 03 -> 0 * 5^1 + 3 * 5^0 = 3

Now using Lucas algorithm, 6C3 mod 5 is ((1C0 mod 5) * (1C3 mod 5)) mod 5

Pascal's triangle helps us quickly find the values for nck mod p

Pascal's triangle for mod 5

**In pascal's triangle p[i][j]=p[i-1][j-1]+p[i-1][j]**

1           -> 0th row
1 1         -> 1st row
1 2 1       -> 2nd row
1 3 3 1     -> 3rd row
1 4 1 4 1   -> 4th row (the reason why 3rd column here is 1 is (3+3)%5=1)

So, eg: 4C2 will be 1, 4C1 will be 4, 3C1 will be 3 and so on...

Hence 6C3 mod 5  = ((1C0 mod 5) * (1C3 mod 5)) mod 5
                 = (p[1][0] * p[1][3]) % 5
                 = (1 * 0) % 5
                 = 0


**Chinese reminder theorem(CRT): The reason we need to use CRT is because the Lucas algorithm works for only prime modulo(10 is not a prime), so now to get nCk mod 10 from nCk mod 2 and nCk mod 5, we use CRT.**

![image.png](https://assets.leetcode.com/users/images/d641fbb8-14f3-4bce-b2ae-e766d3ec6684_1740298714.0907393.png)


# Complexity
- Time complexity:
O(n*logn) -> where log here is with base 5.

- Space complexity:
We don't use any extra space hence it's O(1)

# Code
```java []
class Solution {
    public boolean hasSameDigits(String s) {
        int n=s.length()-2,x=0,y=0;
        for(int k=0;k<=n;k++){
            int bcoeff=binMod10(n,k);
            x=(x+((s.charAt(k)-'0')*bcoeff))%10;
            y=(y+((s.charAt(k+1)-'0')*bcoeff))%10;
        }
        return x==y;
    }
    // Use chinese reminder theorem to combine binMod2 and binMod5
    public int binMod10(int n,int k){
        int bm2=binMod2(n,k);
        int bm5=binMod5(n,k);
        for(int x=0;x<=9;x++){
            if(x%2==bm2 && x%5==bm5) return x;
        }
        return 0;
    }
    // Find binMod2 using Lucas algorithm, simplified since it's 2
    // See the explaination why this will work
    public int binMod2(int n,int k){
        return (n&k)==k ? 1 : 0;
    }
    // Find binMod5 using Lucas algorithm
    public int binMod5(int n,int k){
        int pascalTriangleMod5[][] = {
            {1},
            {1,1},
            {1,2,1},
            {1,3,3,1},
            {1,4,1,4,1}
        };
        int ans=1;
        while(n>0 || k>0){
            int ndigit=n%5,kdigit=k%5;
            if(kdigit>ndigit) return 0;
            ans=(ans*pascalTriangleMod5[ndigit][kdigit])%5;
            n/=5;k/=5;
        }
        return ans;
    }
}
```
['Math', 'Java']