Ultra-Fast C++ Lucas Theorem & CRT Approach for Adjacent Sum Reduction (100% Speed & Memory)
IntuitionThe problem requires repeatedly replacing each pair of consecutive digits with their sum taken modulo 10 until only two digits remain. This process can
# Intuition
The problem requires repeatedly replacing each pair of consecutive digits with their sum taken modulo 10 until only two digits remain. This process can actually be "compressed" into a single weighted sum where the weights are the binomial coefficients. In simpler terms, the final two digits are determined by a sum of differences between adjacent digits, each multiplied by a certain binomial coefficient (with all computations done modulo 10).

Since 10 factors into 2 and 5, we can compute each binomial coefficient by separately calculating its remainder when divided by 2 and when divided by 5, and then combine these results using the Chinese Remainder Theorem.

For the remainder modulo 2, there's a well-known trick: the binomial coefficient "C(m, j)" (read as "m choose j") is equal to 1 modulo 2 exactly when every bit that is 1 in j is also 1 in m. In other words, when you perform a bitwise AND of m and j, you will get j if and only if C(m, j) modulo 2 equals 1.

For the remainder modulo 5, Lucas's theorem can be used. However, because both the modulus 5 and the maximum number of digits required to represent m in base-5 (at most 8 digits for m up to 100,000) are small, we can precompute a tiny 5 by 5 table for "C(a, b) modulo 5" for values of a and b between 0 and 4. Then, for each j, we convert j into base-5 and use this table (as per Lucas’s theorem) to quickly calculate C(m, j) modulo 5.

Finally, by combining the two remainders (one from modulo 2 and one from modulo 5) using the Chinese Remainder Theorem, we determine the final coefficient modulo 10. Summing the weighted differences (each difference between consecutive digits times its computed coefficient) tells us whether the final two digits are the same (this will be the case exactly when the overall sum is 0 modulo 10).

# Approach
1. **Precompute Base-5 Digits:**  
   Since m (which equals n minus 2) is relatively small, convert m into its base-5 digits and store them in an array. This avoids any extra overhead from dynamic memory allocation.

2. **Small Combination Table for Modulo 5:**  
   Build a fixed 5 by 5 table for the binomial coefficients "C(a, b)" computed modulo 5 for a, b in the range 0 to 4. Then, for each j from 0 to m, convert j into base-5 and use the table (using Lucas’s theorem) to quickly compute C(m, j) modulo 5.

3. **Bit-Level Trick for Modulo 2:**  
   Use the property that C(m, j) modulo 2 equals 1 if and only if each bit in j is also set in m. This is efficiently determined by checking whether (m AND j) equals j.

4. **Combine Using the Chinese Remainder Theorem (CRT):**  
   With the two remainders available - call the modulo 2 remainder "c2" and the modulo 5 remainder "c5" - find the unique number between 0 and 9 that satisfies:
   - The number gives a remainder of c5 when divided by 5, and
   - The number gives a remainder of c2 when divided by 2.
   
   Since c5 is less than 5, we can simply add 5 to c5 if its parity does not match c2.

5. **Accumulate the Result & Decide:**  
   Loop over every j from 0 to m (where each j corresponds to one term in the weighted sum). For the given digit string, sum up the differences (s[j] minus s[j+1]) each multiplied by the corresponding coefficient computed in the steps above. Finally, if the overall sum (reduced modulo 10) equals 0, then the two remaining digits are the same.

# Complexity
- **Time Complexity:**
O(n) – We iterate from j = 0 to m (with m equal to n minus 2). In each iteration, an inner loop runs at most 8 times (since the number of base-5 digits is at most 8), which is constant.
- **Space Complexity:**
O(1) – Only fixed-size arrays are used, in addition to the input string.

# Code
```cpp
#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    bool hasSameDigits(string s) {
        int n = s.size();
        // 'm' is the number of rounds we'll effectively perform (since we stop once we have 2 digits left)
        int m = n - 2;
        
        // Here we convert 'm' into its base-5 representation.
        // For m up to about 100,000, its base-5 form will have at most 8 digits.
        // Since we know the maximum size is small, we use a fixed-size array instead of a dynamic one.
        int m_digits[10], m_size = 0;
        int temp = m;
        if (temp == 0) {
            m_digits[m_size++] = 0;
        } else {
            while (temp > 0) {
                m_digits[m_size++] = temp % 5;  // get the next digit in base 5
                temp /= 5;
            }
        }
        
        // This is a precomputed 5x5 table that holds the values for the binomial coefficients "C(a, b)"
        // (which means "a choose b") after we take the remainder when dividing by 5.
        // We have this table for a and b in the set {0, 1, 2, 3, 4}.
        // For situations where b is larger than a, we define C(a, b) to be 0.
        const int small[5][5] = {
            {1, 0, 0, 0, 0},
            {1, 1, 0, 0, 0},
            {1, 2, 1, 0, 0},
            {1, 3, 3, 1, 0},
            {1, 4, 1, 4, 1}
        };
        
        // 'diff' will hold our running total. In the end, if 'diff' is 0 (after reducing modulo 10),
        // that means the final two digits are the same.
        int diff = 0;
        
        // Now we loop over every j from 0 to m (inclusive). Each j corresponds to one term in the weighted sum.
        for (int j = 0; j <= m; j++) {
            // First, we want to compute (m choose j) but only care about its value modulo 5.
            // Instead of calling a separate function, we calculate it inline.
            int res5 = 1;
            int x = j;
            // Process each digit (in base-5) of j alongside the corresponding digit of m.
            for (int i = 0; i < m_size; i++) {
                int d = x % 5;  // extract the i-th digit of j in base 5
                x /= 5;
                int a = m_digits[i];  // get the corresponding digit of m in base 5
                // If the digit of j is greater than the digit of m at this position,
                // then (m choose j) is 0 (when considered modulo 5)
                if (d > a) { 
                    res5 = 0;
                    break;
                }
                // Otherwise, multiply our result by the precomputed value from our table,
                // and then take the remainder after dividing by 5.
                res5 = (res5 * small[a][d]) % 5;
            }
            
            // Next, we compute the remainder of (m choose j) when dividing by 2 using a neat bit trick.
            // The idea is: (m choose j) leaves a remainder of 1 when divided by 2 if and only if every bit set
            // in j is also set in m. We can quickly check that with a bitwise AND.
            int c2 = ((m & j) == j) ? 1 : 0;
            
            // Now we want to merge the two remainders (the one modulo 5 we computed in res5,
            // and the one modulo 2 stored in c2) into a final coefficient in the range 0 to 9.
            // We need a number that, when divided by 5, gives us res5, and when divided by 2, gives us c2.
            // Since res5 is between 0 and 4, it might already have the correct even/odd value (parity).
            // If it does, we use it directly; if not, we add 5 to flip the parity.
            int coeff = ((res5 & 1) == c2) ? res5 : res5 + 5;
            
            // Now, we take the difference between the digit at position j and the digit at position j+1.
            // We multiply this difference by our coefficient and add it to the running total 'diff'.
            // We use modulo 10 to keep the result within the 0 to 9 range.
            int delta = (s[j] - '0') - (s[j + 1] - '0');
            diff = (diff + coeff * delta) % 10;
            if (diff < 0)
                diff += 10;
        }
        
        // Finally, if diff is 0 (after taking mod 10), it means the two remaining digits are the same.
        return diff == 0;
    }
};
```
['Bit Manipulation', 'Combinatorics', 'C++']