🔥🔥Luca's Theorem 🔥| Combinatorics | Easy, when you do dry run or hard forever 🔥🔥|
IntuitionApproachN = [N1, N2, ... N-kth term] in p base
M = [M1, M2, ... M-kth term] in p base
p is a prime and may or may not multiple of N or MThen, according
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
N = [N1, N2, ... N-kth term] in p base
M = [M1, M2, ... M-kth term] in p base
p is a prime and may or may not multiple of N or M

Then, according to Lucas Theorem -->
    c(N, M) = N! / (M! * (N-M)!)


    c(N, M) % p = c(N1, M1) * c(N2, M2) * ... * c(N(kth term), M(kth term)) % p

Afterthat, by breaking down binomial coefficients modulo10 using mod 2 and mod5 separately and then reconstructing them via the Chinese Remainder Theorem(CRT), the approach avoids redundant calculations, making it highly efficient.

# 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
```cpp []
// If gcd(b, mod) != 1 (No Modular Inverse Exists)
// Here, mod is very low, so Simple moduler division is not possible here.
// That's why we need to use some other theorem i.e, Luca's Theorem

class Solution {
public:
    int nCr(int n, int r) {
        int ans = 1 ;

        for(int i=1 ; i<=r ; i++) 
        {
            ans *= n-i+1 ;
            ans /= i ;   // Here No problem will occur, because [r < mod]. And mod is very small, as well as we are not doing any moduler operations
        }

        return ans ;
    }

    int nCr_mod_Lucas_Theorem(int n, int r, int mod)
    {
        if(r > n) return 0 ;

        int res = 1 ;
        while(n>0 && r>0) 
        {
            res *= nCr(n%mod, r%mod) ;
            res %= mod ;

            n /= mod ;
            r /= mod ; 
        }

        return res ;
    }

    bool hasSameDigits(string s) {
        int n = s.length() ;

        int num1 = 0, num2 = 0 ;

        for(int i=0 ; i<n-1 ; i++) 
        {
            int res2 = nCr_mod_Lucas_Theorem(n-2, i, 2) ; // Instead -> return ((n&r) == r) ;
            int res5 = nCr_mod_Lucas_Theorem(n-2, i, 5) ;
            int res10 = -1 ;

            for(int decimalVal=0 ; decimalVal<=9 ; decimalVal++) 
            {
                if(decimalVal%2 == res2 && decimalVal%5 == res5) 
                {
                    res10 = decimalVal ;
                }
            }

            num1 = (num1 + res10 * (s[i]-'0')) % 10 ;
            num2 = (num2 + res10 * (s[i+1]-'0')) % 10 ;
        }    

        return num1 == num2 ;
    }
};

```

![LC UPVOTE.jpeg](https://assets.leetcode.com/users/images/e02302f5-c506-41c3-a017-33c12f074ff2_1740302384.4993923.jpeg)
['Math', 'Combinatorics', 'Number Theory', 'C++']