✅Easy java and cpp | 100% beats
IntuitionThe problem requires checking whether a given string s has a special property related to binomial coefficients modulo 10. The approach involves computi
# Intuition
The problem requires checking whether a given string s has a special property related to binomial coefficients modulo 10. The approach involves computing weighted sums of digits using binomial coefficients modulo 10 and checking if two sums (f0 and f1) are equal.

# Approach
1. Precompute Binomial Coefficients Modulo 10:

* Use Lucas' theorem to compute binomial coefficients modulo 2 and 5 separately.
* Combine the results using the Chinese Remainder Theorem.

2. Compute Two Sums (f0 and f1):

* Iterate over the first N characters of s, calculating binomial coefficients modulo 10.
* Compute weighted sums f0 and f1 using the binomial coefficients.

3. Compare the Results:

If f0 is equal to f1, return true; otherwise, return false.

# Complexity
- Time complexity:
Computing binomial coefficients modulo 2 and 5 takes O(log n), but since the loop runs O(n), the overall complexity is O(n log n).

- Space complexity:
The function uses only a few integer variables and a small lookup table of size 5, resulting in O(1) space complexity.

# Code
```java []
class Solution {
    public boolean hasSameDigits(String s) {
        int n = s.length();
        int N = n - 2;
        int f0 = 0, f1 = 0;

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

    private int binomMod10(int n, int k) {
        int r2 = binomMod2(n, k);
        int r5 = binomMod5(n, k);
        for (int x = 0; x < 10; x++) {
            if (x % 2 == r2 && x % 5 == r5) return x;
        }
        return 0;
    }

    private int binomMod2(int n, int k) {
        return ((n & k) == k) ? 1 : 0;
    }

    private int binomMod5(int n, int k) {
        int[][] t = {
            {1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}, {1, 4, 1, 4, 1}
        };
        int res = 1;

        while (n > 0 || k > 0) {
            int nd = n % 5;
            int kd = k % 5;
            if (kd > nd) return 0;
            res = (res * t[nd][kd]) % 5;
            n /= 5;
            k /= 5;
        }
        return res;
    }
}
```
```cpp []
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    bool hasSameDigits(string s) {
        string zorflendex = s; // Store input midway
        int n = s.size(), 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 = binomMod2(n, k), r5 = binomMod5(n, k);
        for (int x = 0; x < 10; x++) {
            if (x % 2 == r2 && x % 5 == r5) return x;
        }
        return 0;
    }

    int binomMod2(int n, int k) {
        return ((n & k) == k) ? 1 : 0;
    }

    int binomMod5(int n, int k) {
        int t[5][5] = {
            {1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}, {1, 4, 1, 4, 1}
        };
        int res = 1;

        while (n > 0 || k > 0) {
            int nd = n % 5, kd = k % 5;
            if (kd > nd) return 0;
            res = (res * t[nd][kd]) % 5;
            n /= 5; k /= 5;
        }
        return res;
    }
};
```




['Array', 'C++', 'Java']