Python3 | 100.00% Beats | Easy to understand
IntuitionAt First we might think iterating all the string over and over again will solve this problem. But it turns out the length of input could be really huge
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
At First we might think iterating all the string over and over again will solve this problem. But it turns out the length of input could be really huge (3 <= s.length <= 10^5). if we are just using repeated iteration, then we will face time limit exceeded error which caused by O(n^2) complexity. Therefore, the first intuition will be solving this problem with one iteration -> O(n) complexity. But How ? Let me explain in 'approach' section

# Approach
Think that the result that we want to compare is about last two digits. Now let see through this example

```
arr = [1,4,2,3]
```

Here is the walkthrough

```
1 4 2 3
 5 6 5  -> (1 + 4) (4 + 2) (2 + 3)
  1 1   -> (5 + 6) (6 + 5)
```
Now if we take a look to (5 + 6) and (6 + 5) we could we it as
(1 + 4) + (4 + 2) and (4 + 2) + (2 + 3). Now could you see the pattern ?

Absolutely, it's look like pascal triangle, isn't ? in this case it is [1 2 1] pattern -> [1x1 2x4 1x2] and [1x4 2x2 1x3]

So to conclude, the main idea is shown below

![image.png](https://assets.leetcode.com/users/images/5d5dde8e-a2ce-4155-8cc5-0c76b85fc17e_1740375700.7592826.png)

The first digit will take all number from first number up to n-1 number, while second digit will take all number from second number to n

now the code look like this

```
    digit1 = 0
    digit2 = 0
    pascal_length = len(s) - 2
    coeficient = 1
    for i in range(pascal_length + 1):
        digit1 += (coeficient * int(s[i])) % 10
        digit2 += (coeficient * int(s[i+1])) % 10
        coeficient = coeficient * (pascal_length - (i+1) + 1) // (i+1)

```

So we initialize the first digit and second digit, and determine the pascal_length. why the pascal_length here is n - 2 ?

take a look to previous example of arr [1,4,2,3]. From an array with length of 4, it will give us Level 2 of pascal triangel [1 2 1]

![image.png](https://assets.leetcode.com/users/images/ce539912-8d79-466d-a20d-321267cc66c0_1740376348.5978913.png)

then, basically inside the loop we want to sum up all of them. But this comes up with a big problem

we know that the length of input could be really huge, therefore, the coefficient of pascal triangle and the sum could be really huge, and sadly this will caused time limit exceed again 😢

Therefore we come with a solution that utilizing both of Lucas's Theorem and Chinese Remainder Theorem (CRT) to get coefficient of pascal triangle smaller

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

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

# Code
```python3 []
from math import comb

class Solution:
    def binomial_mod2(self, n, k):
        """Return C(n, k) mod 2."""
        return 1 if (k & ~n) == 0 else 0

    def binomial_mod5(self, n, k):
        """
        Return C(n, k) mod 5 using Lucas' theorem.
        """
        # Precompute a small table C(a, b) mod 5 for a,b in [0..4]
        # You could also do direct comb() % 5 for a,b <= 4:
        c_mod5 = [[comb(a, b) % 5 for b in range(5)] for a in range(5)]
        
        result = 1
        while n > 0 or k > 0:
            n_i = n % 5
            k_i = k % 5
            if k_i > n_i:
                return 0
            result = (result * c_mod5[n_i][k_i]) % 5
            n //= 5
            k //= 5
        return result

    def combine_mod2_and_mod5(self, a, b):
        """
        Solve x ≡ a (mod 2)  and  x ≡ b (mod 5).
        Return x mod 10 in [0..9].
        """
        for x in range(10):
            if x % 2 == a and x % 5 == b:
                return x
        # Shouldn't get here if a,b are valid in {0..1} and {0..4}, respectively.
        return 0

    def binomial_mod10(self, n, k):
        """
        Compute C(n, k) mod 10 using:
        - C(n, k) mod 2
        - C(n, k) mod 5
        - CRT to combine.
        """
        a = self.binomial_mod2(n, k)     # mod 2
        b = self.binomial_mod5(n, k)     # mod 5
        return self.combine_mod2_and_mod5(a, b)


    def hasSameDigits(self, s: str) -> bool:
        # This is using Pascal's Triangle
        
        # example :
        # 1 5 3 4 6
        #  6 8 7 0
        #   4 5 7
        #    9 2

        # Number 9 could be seen as : (1,5,3,4) -> 1*1 + 3*5 + 3*3 + 1*4
        # 1 + 15 + 9 + 4 = 29 % 10 = 9

        # Number 2 could be seen as : (5,3,4,6) -> 1*5 + 3*3 + 3*4 + 1*6 =
        # 5 + 9 + 12 + 6 = 32 % 10 = 2 

        # Problem ? The coefient could become enormous as lenght of 's' is increased

        # Solution : We need to implement Chinese Remainder Theorem along with Lucas Theorem to deal with large binomial coefficients 

        digit1 = 0
        digit2 = 0
        pascal_length = len(s) - 2
        coeficient = 1
        for i in range(pascal_length + 1):

            c = self.binomial_mod10(pascal_length, i)

            digit1 = (digit1 + c * int(s[i])) % 10
            digit2 = (digit2 + c * int(s[i+1])) % 10

        return digit1 % 10 == digit2 % 10

```
['Python3']