No Lucas
IntuitionLet the given number bed0​d1​d2​...dn−1​. On iteratively adding the digits as stated in the problem, the final two digits would be:
n−2C0​ d0​+n−2C1​ d
# Intuition
Let the given number be  $$d_0 d_1 d_2 ... d_{n-1}$$. On iteratively adding the digits as stated in the problem, the final two digits would be:

1. $$^{n-2}C_{0}\ d_0 + ^{n-2}C_{1}\ d_1 + ^{n-2}C_{2}\ d_2 + ... ^{n-2}C_{n-2}\ d_{n-2} $$
2. $$^{n-2}C_{0}\ d_1 + ^{n-2}C_{1}\ d_2 + ^{n-2}C_{2}\ d_3 + ... ^{n-2}C_{n-2}\ d_{n-1} $$

# Challenge
<!-- Describe your approach to solving the problem. -->
The main and only challenge in the calculation is modulo 10 being asked in the problem. As 10 is not a prime number modulo inverse does not always exist, causing it difficult to compute the required divisions over modulo.

# Approach
To tackle this problem, as 10 can be prime factorized as $$2 \times 5$$, we compute the binomial coefficient at every step by keeping track of the value using three different values as $$\ x,\ y\ $$and$$\ z$$, where:
1. $$x\ $$ is the power of 2
2. $$y\ $$ is the power of 5
3. $$z\ $$ is the remaining factor
i.e. assume we are computing $$^{n-2}C_{i}\ $$, then: $$^{n-2}C_{i}\ = 2^{x}\  5^{y}\ z$$

We will also be employing the relation (here $$\ m\ $$ would be $$\ n-2\ $$):
 $$^{m}C_{i+1}=^{m}C_{i}\ \frac{m-r}{r+1}$$ 


## NOTE:
In the modInverse calculation, `3` is passed as the second parameter to `powerMod` because $$\phi(10) = 4\ $$. This is from Euler's theorem for modular inverse, which states:
> For any number $${m}$$ where $$gcd(a, m)=1$$:
$$a^{\phi(m)}\equiv1\ (mod\ m)$$
$$a^{-1}\equiv\ a^{\phi(m)-1}\ (mod\ m)$$

1. $$\phi(m)$$ is Euler's totient function whose value is number of coprimes to $$m$$ which are $$\ \leq m$$. 
2. For a number $$m=p_1 ^{x_1}\ p_2 ^{x_2}\ p_3 ^{x_3}\ ...p_k ^{x_k}\ $$:
 $$\phi(m) = m\ (1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})\ ...\ (1-\frac{1}{p_k})$$
3. Hence $$\ \phi(10) = 10 \times (1-\frac{1}{2})\times(1-\frac{1}{5})=4$$
```
int modInverse(int a) {
    return powerMod(a, 3);
}
```

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

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

# Code
```cpp []
class Solution {
public:
    int powerMod(int a, int b) {
        int mod = 10;
        int res = 1;
        a = a % mod;
        while (b > 0) {
            if (b & 1)
                res = (1LL * res * a) % mod;
            a = (1LL * a * a) % mod;
            b >>= 1;
        }
        return res;
    }
    
    int modInverse(int a) {
        return powerMod(a, 3);
    }

    int calc(int x, int y, int z)
    {
        int ans=powerMod(2, x);
        ans=(ans*powerMod(5, y))%10;
        ans=(ans*z)%10;

        return ans;
    }

    bool hasSameDigits(string s) {
        int n=s.size();

        int m=n-1;

        int x=0, y=0, z=1;
        int a=0;
        for(int i=0; i<m; i++)
        {
            int c=s[i]-'0';

            int f=calc(x, y, z);
            a=(a+(c*f)%10)%10;
            
            int num=m-1-i;
            int den=i+1;
            while(num>0 && num%2==0) ++x, num/=2;
            while(den>0 && den%2==0) --x, den/=2;
            while(num>0 && num%5==0) ++y, num/=5;
            while(den>0 && den%5==0) --y, den/=5;

            num%=10;

            z=(((z*num)%10)*modInverse(den))%10;
        }

        x=0, y=0, z=1;
        int b=0;
        for(int i=0; i<m; i++)
        {
            int c=s[i+1]-'0';

            int f=calc(x, y, z);
            b=(b+(c*f)%10)%10;
            
            int num=m-1-i;
            int den=i+1;
            while(num>0 && num%2==0) ++x, num/=2;
            while(den>0 && den%2==0) --x, den/=2;
            while(num>0 && num%5==0) ++y, num/=5;
            while(den>0 && den%5==0) --y, den/=5;

            num%=10;

            z=(((z*num)%10)*modInverse(den))%10;
        }

        return a==b;
    }
};
```
['C++']