Lucas' theorem || Explained
IntuitionThe problem requires us to repeatedly transform a string of digits until only two digits remain, then check if they are equal. Instead of simulating th
### Intuition
The problem requires us to repeatedly transform a string of digits until only two digits remain, then check if they are equal. Instead of simulating the entire transformation process, we can leverage combinatorial mathematics and number theory (Lucas' theorem) to determine the final two digits directly.

### Approach
1. **Understanding the Transformation:**  
   - Each transformation step replaces the string with a new sequence where each digit is calculated as `(s[i] + s[i+1]) % 10`.
   - The number of digits reduces in each iteration until only two remain.

2. **Optimization Using Combinatorial Coefficients:**  
   - Instead of simulating every step, we can compute the final two digits using **binomial coefficients modulo 10**.
   - The approach is based on properties of **Lucas' theorem** for modulus 5 and properties of binomial coefficients modulo 2.

3. **Precomputing Small Binomial Coefficients Modulo 5:**  
   - We precompute binomial coefficients modulo 5 up to size 5.
   - This allows us to efficiently compute any binomial coefficient modulo 5 using **Lucas' theorem**.

4. **Using Lucas' Theorem for Modulo 5 Computation:**  
   - We define a function `lucas_mod5(n, k)`, which calculates binomial coefficients using the theorem.
   - This theorem breaks down `C(n, k) mod 5` into smaller calculations based on digits in base 5.

5. **Calculating the Coefficients for Each Digit:**  
   - The binomial coefficient modulo 2 is determined using `(m & j) == j`.
   - The modulo 5 result is adjusted so that it remains congruent modulo 2.
   - The final coefficient is used to determine the weighted sum of digits.

6. **Computing the Final Two Digits:**  
   - Using the derived coefficients, we compute two final sums and return `true` if they are equal.

### Complexity Analysis
- **Time Complexity:**  
  - Computing binomial coefficients up to size 5 is **O(1)**.
  - The transformation calculations require **O(n)** operations.
  - Overall, the approach runs in **O(n)** time.

- **Space Complexity:**  
  - Only a few integer variables and a small coefficient table are used.
  - The space complexity is **O(1)**.

### Code
```cpp
class Solution {
public:
    bool hasSameDigits(string s) {
        int n = s.size();
        int m = n - 2;
        
        // Precompute small binomials mod 5 for Lucas' theorem.
        int comb[5][5] = {0};
        for (int i = 0; i < 5; i++){
            for (int j = 0; j <= i; j++){
                if (j == 0 || j == i)
                    comb[i][j] = 1;
                else 
                    comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % 5;
            }
        }
        
        // Lucas' theorem for p = 5.
        auto lucas_mod5 = [&](int n, int k) -> int {
            int res = 1;
            while (n > 0 || k > 0) {
                int n_i = n % 5;
                int k_i = k % 5;
                if (k_i > n_i) return 0;
                res = (res * comb[n_i][k_i]) % 5;
                n /= 5;
                k /= 5;
            }
            return res;
        };
        
        // For m = n-2, binom(m, j) mod 2 is 1 if (m & j) == j, else 0.
        auto getCoeff = [&](int j) -> int {
            int a = ((m & j) == j) ? 1 : 0;
            int b = lucas_mod5(m, j); // b is in {0,1,2,3,4}
            int coeff;
            if ((b % 2) == a)
                coeff = b;
            else 
                coeff = (b + 5) % 10;  // b+5 is in {5,6,7,8,9}
            return coeff;
        };
        
        // Compute the two sums:
        int sum0 = 0, sum1 = 0;
        for (int j = 0; j <= m; j++) {
            int coeff = getCoeff(j);
            int digit0 = s[j] - '0';
            int digit1 = s[j+1] - '0';
            sum0 = (sum0 + coeff * digit0) % 10;
            sum1 = (sum1 + coeff * digit1) % 10;
        }
        return sum0 == sum1;
    }
};

['Math', 'Number Theory', 'C++']