Check If Digits Are Equal in String After Operations II || Beat 100% Time and Space
Beat 100% Time and Space Complexity Solution for "Check If Digits Are Equal in String After Operations II"This solution efficiently solves the problem using mat
# Beat 100% Time and Space Complexity Solution for "Check If Digits Are Equal in String After Operations II"

This solution efficiently solves the problem using mathematical insights from combinatorics, modular arithmetic, and Lucas's theorem. The approach avoids repeated string manipulations and leverages precomputed mappings to achieve optimal performance.

---

## Intuition

The problem involves repeatedly summing consecutive digits modulo 10 until only two digits remain. Instead of simulating this process iteratively (which would be computationally expensive for large strings), we recognize that the final result depends on weighted sums of the original digits, where the weights are determined by binomial coefficients modulo 10. Using properties of modular arithmetic and Lucas's theorem, we can compute these weights efficiently.

---

## Approach

1. **Key Insight**:
   - The final two digits after all operations depend on weighted sums of the original digits.
   - These weights are given by binomial coefficients $ C(L, j) \mod 10 $, where $ L = n - 2 $ (length of the string minus 2).

2. **Efficient Computation**:
   - Use Lucas's theorem to compute $ C(n, k) \mod 5 $ efficiently.
   - Combine results modulo 2 and modulo 5 to determine $ C(n, k) \mod 10 $ using a precomputed mapping.

3. **Implementation Steps**:
   - Precompute mappings for $ C(n, k) \mod 10 $ based on its behavior modulo 2 and modulo 5.
   - Compute the weighted sums $ f_0 $ and $ f_1 $ for the first $ L+1 $ and last $ L+1 $ digits, respectively.
   - Compare $ f_0 $ and $ f_1 $. If they are equal, return `true`; otherwise, return `false`.

4. **Optimization**:
   - Avoid redundant calculations by leveraging bitwise operations for modulo 2 checks.
   - Use precomputed small binomial coefficients modulo 5 for efficient computation.

---

## Complexity

- **Time Complexity**: $ O(n) $
  - Each digit is processed once, and binomial coefficients are computed in constant time using precomputed tables.
  
- **Space Complexity**: $ O(1) $
  - The solution uses a fixed amount of space for precomputed mappings and temporary variables.

---

## Code

```java
class Solution {
    // Precomputed mapping for nCr mod 10:
    private static final int[][] MOD10_MAPPING = {
        {0, 6, 2, 8, 4}, // when nCr mod2 = 0
        {5, 1, 7, 3, 9}  // when nCr mod2 = 1
    };

    public boolean hasSameDigits(String s) {
        int n = s.length();
        int L = n - 2; // Length of the final operation sequence
        int f0 = 0, f1 = 0;

        // Compute weighted sums for indices 0..L and 1..(L+1)
        for (int j = 0; j <= L; j++) {
            int coeff = binomMod10(L, j); // Binomial coefficient mod 10
            f0 = (f0 + coeff * (s.charAt(j) - '0')) % 10;
            f1 = (f1 + coeff * (s.charAt(j + 1) - '0')) % 10;
        }

        return f0 == f1;
    }

    // Compute nCr mod 10 by combining mod2 and mod5 parts
    private int binomMod10(int n, int k) {
        int mod2 = binomMod2(n, k); // Either 0 or 1
        int mod5 = binomMod5(n, k); // Value in {0,1,2,3,4}
        return MOD10_MAPPING[mod2][mod5];
    }

    // nCr mod 2: nCr mod 2 == 1 if and only if every 1-bit in k is contained in n
    private int binomMod2(int n, int k) {
        return ((n & k) == k) ? 1 : 0;
    }

    // nCr mod 5 computed via Lucas's theorem
    private int binomMod5(int n, int k) {
        // Precomputed small binomial coefficients mod 5 for numbers 0..4
        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 nDigit = n % 5;
            int kDigit = k % 5;
            if (kDigit > nDigit) return 0;
            res = (res * t[nDigit][kDigit]) % 5;
            n /= 5;
            k /= 5;
        }
        return res;
    }
}
['Math', 'Combinatorics', 'Java']