Binomial coefficient | Simple solution with 100% beaten
Has Same Digits CheckIntuitionThe goal is to check if a given string of digits can be reduced to two identical digits using a transformation rule based on binom
# Has Same Digits Check

## Intuition
The goal is to check if a given string of digits can be reduced to two identical digits using a transformation rule based on binomial coefficients modulo 10.

## Approach
1. Compute binomial coefficients modulo 10 efficiently using properties of mod 2 and mod 5.
2. Use the Chinese Remainder Theorem to combine results.
3. Sum the transformed digits and check if the last two remaining digits are the same.

## Complexity
- **Time Complexity:** $$O(n \log n)$$ due to efficient binomial coefficient calculations.
- **Space Complexity:** $$O(1)$$ since we use only a few integer variables.

## Code
```cpp
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    bool hasSameDigits(string s) {
        int n = s.size();
        if (n < 2) return false; // Edge case
        
        int N = n - 2, f0 = 0, f1 = 0;

        for (int j = 0; j <= N; j++) {
            int c = binomMod10(N, j);
            f0 = (f0 + c * (s[j] - '0')) % 10;
            f1 = (f1 + c * (s[j + 1] - '0')) % 10;
        }
        return f0 == f1;
    }

private:
    int binomMod10(int n, int k) {
        int r2 = (n & k) == k; // C(n, k) mod 2
        int r5 = binomMod5(n, k); // C(n, k) mod 5
        return chineseRemainder(r2, 2, r5, 5);
    }

    int binomMod5(int n, int k) {
        static const int t[5][5] = {
            {1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}, {1, 4, 1, 4, 1}
        };
        int res = 1;
        while (n || k) {
            int nd = n % 5, kd = k % 5;
            if (kd > nd) return 0;
            res = (res * t[nd][kd]) % 5;
            n /= 5, k /= 5;
        }
        return res;
    }

    int chineseRemainder(int r1, int m1, int r2, int m2) {
        for (int x = 0; x < m1 * m2; x++) {
            if (x % m1 == r1 && x % m2 == r2) return x;
        }
        return 0;
    }
};
```

['C++']