Intuitive Pascal's triangle approach in C++
IntuitionWhen doing modular arithmetic, taking the mod at the end is equivalent to taking it at the end. So lets just see what the two sums are.Say we have 4 va
# Intuition
When doing modular arithmetic, taking the mod at the end is equivalent to taking it at the end. So lets just see what the two sums are.

Say we have 4 variables x0, x1, x2, x3.

The numbers first become x0 + x1, x1 + x2, x2 + x3.

Then x0 + 2 * x1 + x2, x1 + 2 * x2 + x3

The coefficients of these two equations given the constants is the third row of the pascal triangle. We can prove that this will always be the case for greater amounts of variables as well. (Intuitively, we are always adding together two copies of a Pascal's row, and we are adding them up off by one, which is the definition of Pascal's triangle by induction)

# Approach
We need to calculate a row of pascal's triangle mod 10, and then go through the two sums and use the coefficients from the triangle and the values from the string to see if the two sums are equivalent at the end.

We calculate pascal's triangle mod 10 by using the iterative approach to a row: C(n, k) = C(n, k - 1) * (n - k + 1) / k. However, division is a problem in modular arithmetic. To get around this we use the inverse of the numbers 1, 3, 7, 9 to divide, namely the numbers not divisible by 2 or 5 less than 10. 

We cannot get a multiplicative inverse for numbers divisible by 2 or 5 because they are coprime with 10, which is a huge problem (Look up modular inverse for more details). So instead we store those factors in two variables, and then calculate using fastexp when needed for the actual values in the rows.

After that, we simply add up the sums mod 10 using the values from the row of the Pascal's triangle as coefficients, then return the comparison of the two sums as our answer.

# Complexity
- Time complexity:
We compute an N length row of the pascal's triangle, and then two N factor sums, so O(N)

- Space complexity:
We store an N length row of pascal's triangle, and then some auxilliary memory, so O(N)

# Code
```cpp []
class Solution {
public:

    int fastExp(int base, int exp, int mod = 10) {
        int result = 1;
        while (exp > 0) {
            if (exp % 2 == 1) result = (result * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        } return result;
    }

    const int inv[10] = {1, 1, -1, 7, -1, -1, -1, 3, -1, 9};

    vector<int> generate(int n) {
        vector<int> row(n + 1, 1);
        
        int val = 1, two = 0, five = 0;
        for (int k = 1; k < n; ++k) {
            int mult = n - k + 1, div = k, pval = val;
            while (mult && mult % 2 == 0) { mult /= 2; two++; }
            while (mult && mult % 5 == 0) { mult /= 5; five++; }
            while (div && div % 2 == 0) { div /= 2; two--; }
            while (div && div % 5 == 0) { div /= 5; five--; }
            val = (val * (mult ? mult % 10 : 1) * inv[div % 10]) % 10;

            if (two && five) {
                row[k] = 0;
            } else {
                row[k] = val * fastExp(2, two) * fastExp(5, five) % 10;
            }
        }
        return row;
    }
    bool hasSameDigits(string s) {
        auto v = generate(s.size() - 2);
        int sum1 = 0, sum2 = 0;
        for (int i = 0; i < s.size() - 1; i++) {
            sum1 = (sum1 + v[i] * (s[i] - '0')) % 10;
            sum2 = (sum2 + v[i] * (s[i + 1] - '0')) % 10;
        } return sum1 == sum2;
    }
};
```
['Math', 'Combinatorics', 'C++']