Python: Pascal's Triangle and Modular Multiplicaiton: No Lucas' Theorem
IntuitionCorrelating with binomial coefficients from pascal's triangle to compute weighted sums.3 9 0 2
2 9 2
1 1Looks like a pascal's triangle operation?Pascal
# Intuition
Correlating with binomial coefficients from pascal's triangle to compute weighted sums.

3 9 0 2         
2 9 2           
1 1             

Looks like a pascal's triangle operation?

Pascal's Triangle: -
1
1 1
1 2 1

Observation: -
1 X 3 + 2 X 9 + 1 X 0  (mod 10) = 1 = Ten's digit
1 X 9 + 2 X 0 + 1 X 2  (mod 10) = 1 = One's digit

Easy? Problem: Multiplication too lengthy.

# Approach
L represents a weighted sum of digits from s[0] to s[n-2] with coefficients from n-2 level of pascal's triangle, represented by \combination(n-2  k); where n is the number of digits in s, and k is the current digit position.

Similarly, R represents a weighted sum of digits from s[1] to s[n-1]

Updation of pascal coefficient, pc_k+1 = (n-2  k+1), avoids calculating entire factorials by updating current pc by multiplying by a factor of (n-2 + 1)/(k+1). ( because (n-2  k+1) / (n-2  k) = (n-2 + 1)/(k+1) )

L is the Ten's digit, R is the One's digit.


For the problem of lengthy multiplication we reduce operands in modulo 10. However, 10 is composite. Hence, we must remove its prime factors from the operands i.e {2, 5}.

##### Factor Decomposition
The factors method decomposes each number, x, into the form:

x = 2^a * 5^b * x′ ; gcd(x′, 10)=1

This decomposition is represented as a tuple x -> (x', a, b).

##### Modular Arithmetic

Multiplication modulo 10 is performed using the mod method:

we know now, x ≡ r_x * 2^(a_x) * 5^(b_x) (mod10)

pc_k+1 = pc_k * r_n / r_d * 2^(a_n - a_d) * 5^(b_n - b_d)  (mod 10)

=>  r_k+1 = (r_k * r_n * pow(r_d, -1, 10)) % 10 

which uses modular inverse of r_d  (mod 10) for efficient calculations, which exists because of the decomposition that ensures gcd(r, 10) = 1.

For even more efficiency we are precomputing factor decompositions for all numbers up to n.

# Complexity
- Time complexity: $$O(n)$$
We perform a single pass through the string of length n. 
The factor decomposition is also O(n). It might appear to be O(nlogn) but it is in O(n) as each division step removes a prime factor, factors become sparser as exponents increase. Harmonic series convergence for prime factors. Thus, the overall complexity remains linear relative to the input size max_n.

- Space complexity: $$O(n)$$
We store the prime factorizations of numbers from 1 to n.

# Beautiful Code
```python3 []
class Solution(object):    
    def factors(self, max_n):
        # x -> (x', count_2, count_5); x = 2^(a)*5^(b)*x', gcd(x', 10) = 1.
        fac = [None]*(max_n+1)
        for x in range(1, max_n+1):
            a = b = 0
            temp = x
            while temp%2 == 0:
                a, temp = a+1, temp//2
            while temp%5 == 0:
                b, temp = b+1, temp//5
            fac[x] = (temp, a, b)
        return fac

    def mod(self, r, a, b):
        # pc: (r, a, b); pc = 2^a * 5^b * r.
        # pc % 10 = 0 if at least one factor of 10 appears
        # else pc = (r * 2^a * 5^b) mod 10.
        if min(a, b) > 0:
            return 0
        return (r * pow(2, a, 10) * pow(5, b, 10)) % 10

    def hasSameDigits(self, s):
        """
        :type s: str
        :rtype: bool
        """
        n = len(s)
        L = R = 0

        fac = self.factors(n)
        r, a, b = 1, 0, 0  # c(n-2, 0) = 1; => (r, a, b) = (1, 0, 0)
        for k in range(n-1):
            pc = self.mod(r, a, b)

            L = (L + pc*int(s[k])) % 10
            R = (R + pc*int(s[k+1])) % 10
            
            if k == n-2: break
            # pc = pc * (n-2 - k) / (k+1)
            num = n-2 - k;  rn, a_n, b_n = fac[num]
            den = k+1;      rd, a_d, b_d = fac[den]
            
            r = (r * rn * pow(rd, -1, 10)) % 10
            a = a + a_n - a_d
            b = b + b_n - b_d
        
        return L == R

```
['Python3']