Lucas Theorem
IntuitionFor any string, let's take a look at its digits. This gives us some array of numbersAconsisting of[a1, a2, ..., an].The "next level" after applying one
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
For any string, let's take a look at its digits. This gives us some array of numbers `A` consisting of `[a1, a2, ..., an]`.
The "next level" after applying one operation to our array gives us the new array `A' = [a1+a2, a2+a3, a3+a4, ...]`. When we apply this another time, we get `A'' = [a1+2a2+a3, a2+2a3+a4, a3+2a4+a5, ...]`. We start to see the pattern that on any row, the coefficients are going to be related to the binomial coefficients for the row.

So, we can calculate the binomial coefficients for the two numbers in the last "row" that will appear. This means we'll be choosing numbers from len(s)-2.

# Approach
<!-- Describe your approach to solving the problem. -->

We want to calculate the binomial coefficient for a given i. However, given the large numbers, this won't work. We can use lucas's theorem to make this faster and take advantage of the fact that a combination divisible by 10 won't contribute to the result.

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

# Code
```python3 []
import math


def lucas_theorem(n: int, k: int, p: int):
    # n choose k mod p
    # can be represented with the per-"bit" product
    # see https://en.wikipedia.org/wiki/Lucas%27s_theorem
    product = 1
    while n != 0 or k != 0:
        n_dig = n % p
        k_dig = k % p
        if k_dig > n_dig:
            return 0
        # small enough since we only have 5 and 2
        product *= math.comb(n_dig, k_dig)
        product %= p
        n //= p
        k //= p
    return product


def binom(n, k):
    # figure out the result mod 2 and mod 5
    m2 = lucas_theorem(n, k, 2)
    m5 = lucas_theorem(n, k, 5)

    # hacky way but it works...
    if m2 == 0:
        if m5 == 0:
            return 0
        if m5 == 1:
            return 6
        if m5 == 2:
            return 2
        if m5 == 3:
            return 8
        if m5 == 4:
            return 4
    else:  # m2 == 1
        if m5 == 0:
            return 5
        if m5 == 1:
            return 1
        if m5 == 2:
            return 7
        if m5 == 3:
            return 3
        if m5 == 4:
            return 9
    raise Exception("How??")


class Solution:
    def hasSameDigits(self, s: str) -> bool:
        # doing it the brute force way is N**2 time
        # because we only remove one number each time

        # so when we do the reductions, it looks like just pascal's triangle
        # for the bottom two
        # ie if we have a b c d e
        # then bottom row compares
        # a + 3b + 3c + d vs b + 3c + 3d + e

        # similarly
        # a b c d
        # a + 2b + c vs b + 2c + d
        # and it also works for 6 numbers too
        # so let's just use that to figure out our last row's numbers
        # and then compare them
        # takes like O(N) time to generate each of these
        # so we good
        # the level of the triangle is of len(s) - 2
        # 1 4 6 4 1 -> is from level 4

        # so naive math.comb doesn't work
        # because gets to huge numbers
        # so what we notice is that if the combination is >= 10
        # then it will have no effect on the answer
        # since we only want the last digit
        # hmm
        # ok so let's use some textbook math
        # we can use an extension of lucas's theorem since we know that
        # 10 is exactly 2 * 5 (the product of 2 primes)
        # it'd be a lot easier if it was just a single prime...
        # but oh well we can do this

        n1 = 0
        n2 = 0
        for i in range(len(s) - 1):
            # multiple = math.comb(len(s) - 2, i)
            multiple = binom(len(s)-2, i)
            n1 += multiple * int(s[i]) % 10
            n1 %= 10
            n2 += multiple * int(s[i + 1]) % 10
            n2 %= 10
        return n1 == n2

```
['Python3']