🤯 How to notice that it's Pascal's triangle and compute it if you're not a mathematician 🤯
IntuitionWhen trying a new problem like this, I recommend going through some examples by hand to build up your intuition. I went through the examples given, but
# Intuition

When trying a new problem like this, I recommend going through some examples by hand to build up your intuition. I went through the examples given, but rather than simplifying the numbers at every step, I kept track of how many times each original digit was included in the final results, i.e. its coefficient. The reason I did this is because I'd like to quickly be able to calculate the coefficient -- if we can calculate all the coefficients quickly then we can find out what the final two digits are without going through each intermediate step (which would be $O(n^2)$ complexity, too expensive for the bounds of this problem.)

Let's take a look together. I'm going to omit the mod 10 because we can apply it at the end. It's the intermediate steps that are most interesting.

## Example 1

For 3902, the process goes like:

3, 9, 0, 2
3 + 9, 9 + 0, 0 + 2
(3 + 9) + (9 + 0), (9 + 0) + (0 + 2)

Grouping the digits together we see that the final two digits are:
1 * 3 + 2 * 9 + 1 * 0
and
9 * 1 + 2 * 0 + 1 * 2
So the coefficients of the digits are 1, 2, 1.

---

## Example 2

For 34789, the process goes like:

3, 4, 7, 8, 9
3 + 4, 4 + 7, 7 + 8, 8 + 9
(3 + 4) + (4 + 7), (4 + 7) + (7 + 8), (7 + 8) + (8 + 9)
((3 + 4) + (4 + 7)) + ((4 + 7) + (7 + 8)), ((4 + 7) + (7 + 8)) + ((7 + 8) + (8 + 9))

Conveniently the digits are all unique so grouping the coefficients is not too bad:
1 * 3 + 3 * 4 + 3 * 7 + 1 * 8
and
1 * 4 + 3 * 7 + 3 * 8 + 1 * 9
So the coefficients of the digits are 1, 3, 3, 1.

---

If you're familiar with Pascal's triangle and binomial coefficients, this might already be enough to notice the pattern. But if not, it's totally cool to go through a larger example. Let's try a 6-digit string, but let's use abstract digits:

A, B, C, D, E, F
A + B, B + C, C + D, D + E, E + F
A + 2B + C, B + 2C + D, C + 2D + E, D + 2E + F
A + 3B + 3C + D, B + 3C + 3D + E, C + 3D + 3E + F
A + 4B + 6C + 4D + E, B + 4C + 6D + 4E + F

We can see that the coefficients of the digits in the last row are 1, 4, 6, 4, 1.

Moreover, focusing on the very first element in each row, we can see the entire history of coefficients for smaller examples:

A
A + B
A + 2B + C
A + 3B + 3C + D
A + 4B + 6C + 4D + E

Or:

1
1, 1
1, 2, 1
1, 3, 3, 1
1, 4, 6, 4, 1

Can you predict what the next row of coefficients would be, without having to go through an example? Think about what's happening: at each step we are squashing a bunch of digits together and we can add the coefficients, but we have to do so at an offset, to combine the like digits. A + B squashed together with B + C becomes A + 2B + C. And A + 2B + C squashed together with B + 2C + D becomes A + 3B + 3C + D.

So to get the next row we need to squash two copies of 1, 4, 6, 4, 1 at an offset. Expressed vertically we sum:
1, 4, 6, 4, 1, 0
0, 1, 4, 6, 4, 1

To get:
1, 5, 10, 10, 5, 1

We can verify that these are the correct coefficients by adding the last two digits together that we already computed above, A + 4B + 6C + 4D + E and B + 4C + 6D + 4E + F which indeed become A + 5B + 10C + 10D + 5E + F with coefficients 1, 5, 10, 10, 5, 1.

If we were mathematicians, we might consider a formal proof at this point, but as software engineers, this is good enough to move on.

# Approach

Alright, so if we can figure out the coefficients quickly then we could compute the last two digits with $O(n)$ complexity: just iterate over the digits, multiply by the coefficient, and add. Mod the sum by 10 at each step to keep it one digit. Awesome! So how do we figure out the coefficients quickly?

We can compute each row of coefficients from the previous row. However, if we computed every previous row, thus building the entire (Pascal's) triangle up to the point we care about, that would be $O(n^2)$ complexity. A triangle is half of a square. We could take advantage of symmetry to save another factor of 2 (did you notice that each row of coefficients is the same forwards and backwards?) but that's still not good enough for these bounds. We need some way to compute the last row and last row only.

This is where it kinda helps to know that Pascal's triangle is very related to the binomial coefficients and the combinations formula. Our 1, 4, 6, 4, 1 row is really $\binom{4}{0}$, $\binom{4}{1}$, $\binom{4}{2}$, $\binom{4}{3}$, $\binom{4}{4}$ in disguise. If you knew this then you have a big advantage and can leap to binomial coefficients quickly. If you didn't know this, I recommend [reading about it](https://en.wikipedia.org/wiki/Pascal%27s_triangle#Combinations), but for an idea that might help you figure it out, consider the following:

We started with A, B, C, D, E, F and after squashing digits, our first digit becomes A + 4B + 6C + 4D + E. How come there's only one A but 6 Cs? Well the A in the original digits has only one possible path through the triangle: left, left, left, left. But the C in the original digits has more. To end up in the middle of the pack it needs to take just as many steps left as it does right, but it could do LLRR, RRLL, LRLR, or 3 more options. Expressed combinatorically we must choose 2 out of its 4 steps to be left: 4 choose 2. Hello, combinations formula!

## Division is annoying

To compute combinations, we can use the formula $\binom{n}{k} = \frac{n!}{k! (n-k)!}$. Since we need to do this for all the possible values of $k$, we can compute all of the relevant factorials. The numbers will get rather large, but since we only care about single digits we could mod by 10 along the way. Problem with that approach is it'll mess up our division. Whereas multiplication plays nicely with modulo in that `(a * b) % m == (a % m) * (b % m)` give or take a mod, this is not true for division.

If you didn't know that, I recommend using hours and minutes to practice your intuition for mod, because if you just focus on the number of minutes ignoring the hours, you're doing mod 60 in real life. Here's an example: if I multiply 497 hours and 12 minutes times 7, how many minutes past a whole hour will I have? In other words, what's `((497 * 60 + 12) * 7) % 60`? Hopefully you didn't multiply 497 times 7 to answer -- the hours cancel out if we're focusing on the minutes, i.e. `60 % 60` is just zero.

Now let's try a division. How many minutes past a whole hour will I have if I divide X hours by 4? By the previous logic we might think that the hours cancel out, because `60 % 60` is still zero, but it depends on the value of X. For X = 1, or 1 hour divided by 4, we'll get 15 minutes: `((1 * 60 ) / 4) % 60` is 15. However for X = 3 hours, we'll get 45 minutes: `((3 * 60) / 4) % 60` is 45.

Ok, now that you hopefully believe me that dividing factorials mod 10 isn't trivial, what do we do? Turns out there are situations in which we can divide safely, by turning the divisions into multiplications. For example instead of dividing by 7 we can multiply by 3. Huh???? It's true! Let's say we wanted to know what 864192 / 7 is mod 10 (that number is divisible by 7, I promise). Well, I'm claiming that it's going to be same as 864192 * 3 mod 10. Since this is a multiplication, we can take the mod early and say that it's 2 * 3 or 6. Check it, I dare you!

This works because 7 and 3 cancel each other out when multiplying mod 10. Basically I'm saying that if you multiply some number by 7, and then multiply the result by 3, the final number will end with the same digit as the original number. That's because multiplying it by 7 and then multiplying it by 3 is the same as just outright multiplying it by 21, and since we're focusing on the last digit, multiplying by 21 is no different from multiplying by 1.

In fancy terms, 7 and 3 are multiplicative inverses mod 10. So instead of doing `(x / 7) % 10`, we can compute `(x / 7 * (7 * 3)) % 10`, without affecting the result. As long as `x` is divisible by 7, it's safe to cancel out the division by 7 and the multiplication by 7 to get `(x * 3) % 10`.

So we've figured out that instead of dividing by 7 we can multiply by 3. What else can we divide by? Well, by the symmetric argument, instead of dividing by 3 we can multiply by 7. What else? We can safely divide by 1 by doing nothing. (In fancy terms: 1 is its own multiplicative inverse, just like in standard arithmetic.) Can we divide by any other digits? There's one more. We can replace division by 9 with multiplication by 9, since 9 is also its own multiplicative inverse. Verify that 9 * 9 ends with a 1, or if you want your mind blown consider that 9 is the same as -1 as far as mod 10 is concerned, and -1 is its own multiplicative inverse as well: in standard arithmetic multiplying times -1 and dividing by -1 are equivalent.

But what about all the other digits? How do we divide by 2, 4, 5, 6, or 8? Or by 0? None of these digits have a multiplicative inverse mod 10. That is, there's no way to multiply any of those digits by something and have the result end in 1. For the even digits, any product will forever stay even. And for 5, any product will end either in 5 or in 0.

## Let's work around 2s and 5s

Finally we get to the punch line. Since even numbers and 5s make division annoying, we treat them specially. We won't just naively express each factorial mod 10, we'll express them as tuples of the form (number of twos, number of fives, everything else mod 10). For example, we'll express 1! as (0, 0, 1) because it's composed of 0 twos, 0 fives, and the rest of the product is a 1. 2! = 2 will be expressed as (1, 0, 1) because it's composed of 1 two multiplied by 0 fives multiplied by 1. 3! = 6 will be expressed as (1, 0, 3) i.e. $(2^1)(5^0)(3)$, 4! = 24 will be expressed as (3, 0, 3) i.e. $(2^3)(5^0)(3)$, 5! = 120 will include our first five as (3, 1, 3) also known as $(2^3)(5^1)(3)$.

These tuples are straightforward to multiply:

```python3 []
def mult(a, b):
    return (
        a[0] + b[0],
        a[1] + b[1],
        (a[2] * b[2]) % 10,
    )
```

...and also to divide, because the third element is now guaranteed to be 1, 3, 7, or 9, and we know how to divide by those:

```python3 []
INV = {
    1: 1,
    3: 7,
    7: 3,
    9: 9,
}

def div(a, b):
    return (
        a[0] - b[0],
        a[1] - b[1],
        (a[2] * INV[b[2]]) % 10,
    )
```

To then turn such a tuple into a single digit, we take advantage of the fact that powers of 2 with a positive exponent end with 2, 4, 8, 6, 2, 4, 8, 6, ... ad infinitum. And powers of 5 with a positive exponent all end in 5:

```python3 []
TWOS = [2, 4, 8, 6]
FIVES = [5]
def simplify(tup):
    twos, fives, res = tup

    if twos:
        res = (res * TWOS[(twos - 1) % len(TWOS)]) % 10
    if fives:
        res = (res * FIVES[(fives - 1) % len(FIVES)]) % 10

    return res
```

## Summary of complete approach

1. Compute factorials from 0 to n, expressed as tuples of (number of twos, number of fives, everything else mod 10).
2. Compute binomial coefficients using the combinations formula. Use modular multiplicative inverses to divide the "everything else" part, then simplify to a single digit mod 10.
3. Multiply the digits in the input by the coefficients to get the final two digits and compare them!

## But how do I figure this out in an interview?

You don't. This isn't a software engineering interview problem, it's a math problem. If an interviewer expects you to know this, then you're presumably applying to an applied math position of some kind, so you eat binomial coefficients for breakfast.

Enjoy the math for its beauty and don't worry about seeing something like this in a software engineering interview.

# Complexity
- Time complexity: $O(n)$ if you're not lazy in step 1. I was lazy in step 1 and recomputed the number of twos and fives each time, it's small enough to not matter for these bounds. But you can be clever and do some caching along the way. Specifically notice that the number of twos in the decomposition of some even number N is one more than the number of twos in the decomposition of N / 2.
- Space complexity: $O(n)$ for the factorials and coefficients.

# Code

Here's [my submission](https://leetcode.com/problems/check-if-digits-are-equal-in-string-after-operations-ii/submissions/1552448975/) as I originally wrote it, apologies that it's in Python:

```python3 []
INV = {
    1: 1,
    3: 7,
    7: 3,
    9: 9,
}

def mult(a, b):
    return (
        a[0] + b[0],
        a[1] + b[1],
        (a[2] * b[2]) % 10,
    )

def div(a, b):
    return (
        a[0] - b[0],
        a[1] - b[1],
        (a[2] * INV[b[2]]) % 10,
    )

def red(it):
    return sum((a * b) % 10 for a, b in it) % 10

TWOS = [2, 4, 8, 6]
FIVES = [5]
def simplify(tup):
    twos, fives, res = tup

    if twos:
        res = (res * TWOS[(twos - 1) % len(TWOS)]) % 10
    if fives:
        res = (res * FIVES[(fives - 1) % len(FIVES)]) % 10

    return res

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        n = len(s) - 2
        
        facts = [(0, 0, 1)]
        while n >= len(facts):
            num = len(facts)

            twos = 0
            while num % 2 == 0:
                num //= 2
                twos += 1
        
            fives = 0
            while num % 5 == 0:
                num //= 5
                fives += 1
            
            facts.append(mult(facts[-1], (twos, fives, num)))
        
        pascal = []
        for k in range(n + 1):
            pascal.append(simplify(div(div(facts[n], facts[k]), facts[n - k])))

        a = red(zip(map(int, s), pascal))
        b = red(zip(map(int, s[1:]), pascal))

        return a == b
```
['Python3']