# Check If Digits Are Equal in String After Operations II
**Difficulty:** HARD
[External](https://leetcode.com/problems/check-if-digits-are-equal-in-string-after-operations-ii)
Canonical: https://scaleengineer.com/dsa/problems/check-if-digits-are-equal-in-string-after-operations-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** String
---
## Problem
You are given a string `s` consisting of digits. Perform the following operation repeatedly until the string has **exactly** two digits:

* For each pair of consecutive digits in `s`, starting from the first digit, calculate a new digit as the sum of the two digits **modulo** 10.
* Replace `s` with the sequence of newly calculated digits, _maintaining the order_ in which they are computed.

Return `true` if the final two digits in `s` are the **same**; otherwise, return `false`.

**Example 1:**

**Input:** s = "3902"

**Output:** true

**Explanation:**

* Initially, `s = "3902"`
* First operation:  
  * `(s[0] + s[1]) % 10 = (3 + 9) % 10 = 2`
  * `(s[1] + s[2]) % 10 = (9 + 0) % 10 = 9`
  * `(s[2] + s[3]) % 10 = (0 + 2) % 10 = 2`
  * `s` becomes `"292"`
* Second operation:  
  * `(s[0] + s[1]) % 10 = (2 + 9) % 10 = 1`
  * `(s[1] + s[2]) % 10 = (9 + 2) % 10 = 1`
  * `s` becomes `"11"`
* Since the digits in `"11"` are the same, the output is `true`.

**Example 2:**

**Input:** s = "34789"

**Output:** false

**Explanation:**

* Initially, `s = "34789"`.
* After the first operation, `s = "7157"`.
* After the second operation, `s = "862"`.
* After the third operation, `s = "48"`.
* Since `'4' != '8'`, the output is `false`.

**Constraints:**

* `3 <= s.length <= 105`
* `s` consists of only digits.

# Approaches
## Direct Simulation
This approach directly simulates the process described in the problem. We repeatedly transform the string of digits according to the given operation until its length becomes exactly two. Then, we check if the two final digits are equal.
**Time:** O(n^2), where n is the length of the input string. The outer `while` loop runs `n-2` times. In each iteration `k` (from 0 to n-3), the inner loop runs `n-1-k` times. The total number of operations is the sum `(n-1) + (n-2) + ... + 3`, which is on the order of `n^2`. · **Space:** O(n), where n is the length of the input string. In each step, a new string (or `StringBuilder`) of length one less than the previous is created. The maximum space used is for the string of length n-1.
**Pros:** Simple to understand and implement.; It correctly solves the problem for small input sizes.
**Cons:** The time complexity is quadratic, which is too slow for the given constraints (`s.length` up to 10^5). This will lead to a 'Time Limit Exceeded' (TLE) error on large inputs.
### Explanation
The most straightforward way to solve the problem is to follow the instructions literally. We can use a loop that continues as long as the string's length is more than 2. In each iteration of the loop, we construct the next version of the string by iterating through the current one, taking consecutive pairs of digits, summing them up modulo 10, and appending the result to a new string builder. Once the new string is fully constructed, we replace the old string with it. This process is repeated until the string length is reduced to 2. Finally, we compare the two digits of the resulting string.

```java
class Solution {
    public boolean checkEqual(String s) {
        while (s.length() > 2) {
            StringBuilder next_s = new StringBuilder();
            for (int i = 0; i < s.length() - 1; i++) {
                int digit1 = s.charAt(i) - '0';
                int digit2 = s.charAt(i + 1) - '0';
                int sum = (digit1 + digit2) % 10;
                next_s.append(sum);
            }
            s = next_s.toString();
        }
        return s.charAt(0) == s.charAt(1);
    }
}
```
### Algorithm
- Start a loop that continues as long as the length of the string `s` is greater than 2.
- Inside the loop, create a new `StringBuilder` to build the string for the next iteration.
- Iterate through the current string `s` from the first character up to the second-to-last character.
- For each index `i`, parse the digits at `s[i]` and `s[i+1]`, calculate their sum modulo 10.
- Append the resulting digit to the `StringBuilder`.
- After the inner loop, replace `s` with the string generated by the `StringBuilder`.
- Once the loop terminates (when `s` has a length of 2), compare the two characters of `s`.
- Return `true` if they are equal, and `false` otherwise.

## Combinatorial Formula with Lucas's Theorem
A more efficient approach involves mathematical analysis of the operations. By observing the pattern of how digits combine, we can derive a direct formula for the final digits in terms of the initial digits. This formula involves binomial coefficients. The problem then reduces to checking if a specific weighted sum of the initial digits is zero modulo 10.
**Time:** O(n log n). The modulo 2 check is `O(n)`. The modulo 5 check iterates `n-3` times. Inside the loop, `getCnkModP` takes `O(log_5 n)` time. Thus, the total time is dominated by the modulo 5 check, resulting in `O(n log n)`. · **Space:** O(n) to store the initial digits and the `v` array.
**Pros:** Much more efficient than direct simulation, with `O(n log n)` time complexity.; Avoids creating large intermediate strings, saving on memory operations.
**Cons:** The implementation is complex, requiring knowledge of number theory concepts like Lucas's Theorem and Chinese Remainder Theorem.; The `O(n log n)` complexity might still be too slow if the time limit is very strict, although it's a significant improvement over `O(n^2)`.
### Explanation
Instead of simulating the process, we can find a mathematical shortcut. The final two digits are equal if and only if the first and third digits of the length-3 intermediate string are equal. Let the initial digits be `d_0, ..., d_{n-1}`. After `k` operations, the `i`-th digit is `g_k[i] = sum_{j=0 to k} C(k, j) * d_{i+j}` (mod 10), where `C(k,j)` is the binomial coefficient.

The condition becomes `g_{n-3}[0] == g_{n-3}[2]` (mod 10). This can be shown to be equivalent to checking if `sum_{j=0 to n-3} C(n-3, j) * (d_{j+2} - d_j) == 0` (mod 10).

Let `N = n-3` and `v_j = d_{j+2} - d_j`. We need to compute `Sum = sum_{j=0 to N} C(N, j) * v_j` and check if it's divisible by 10. We do this by checking divisibility by 2 and 5 separately.

**Modulo 2:** `C(N, j) mod 2` is 1 if `(j & N) == j` and 0 otherwise. We can compute the sum `sum_{j | (j&N)==j} v_j` (mod 2) in `O(N)` time.

**Modulo 5:** We need `C(N, j) mod 5`. Using Lucas's Theorem, `C(N, j) mod 5` can be found by comparing the base-5 representations of `N` and `j`. For each `j` from 0 to `N`, we convert `j` to base 5 (`O(log j)`) and compute the coefficient, then add to the sum. This gives an `O(N log N)` algorithm for the modulo 5 check.

```java
class Solution {
    public boolean checkEqual(String s) {
        int n = s.length();
        if (n <= 2) return s.charAt(0) == s.charAt(1);
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = s.charAt(i) - '0';
        }

        int N = n - 3;
        int[] v = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            v[i] = d[i + 2] - d[i];
        }

        // Check modulo 2
        int sumMod2 = 0;
        for (int j = 0; j <= N; j++) {
            if ((j & N) == j) {
                sumMod2 = (sumMod2 + v[j]) % 2;
            }
        }
        if ((sumMod2 + 2) % 2 != 0) return false;

        // Check modulo 5
        int sumMod5 = 0;
        int[][] C_5 = new int[][]{{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}};
        for (int j = 0; j <= N; j++) {
            long c5 = getCnkModP(N, j, 5, C_5);
            long term = (c5 * v[j]) % 5;
            sumMod5 = (int)((sumMod5 + term) % 5);
        }
        if ((sumMod5 + 5) % 5 != 0) return false;

        return true;
    }

    private long getCnkModP(int n, int k, int p, int[][] C_p) {
        if (k < 0 || k > n) return 0;
        long res = 1;
        while (n > 0) {
            int ni = n % p;
            int ki = k % p;
            if (ki > ni) return 0;
            res = (res * C_p[ni][ki]) % p;
            n /= p;
            k /= p;
        }
        return res;
    }
}
```
### Algorithm
- Let the initial digits be `d_0, d_1, ..., d_{n-1}`.
- The condition that the final two digits are equal is equivalent to checking if the first and third digits of the string at length 3 are equal. Let this length-3 string be `[a, b, c]`. We need `a == c` (mod 10).
- The digits `a` and `c` can be expressed as a weighted sum of the initial digits, where the weights are binomial coefficients. Specifically, `a = sum C(n-3, j) * d_j` and `c = sum C(n-3, j) * d_{j+2}`.
- The condition `a == c` (mod 10) becomes `sum_{j=0 to n-3} C(n-3, j) * (d_{j+2} - d_j) == 0` (mod 10).
- Let `N = n-3` and `v_j = d_{j+2} - d_j`. We need to check if `sum_{j=0 to N} C(N, j) * v_j` is a multiple of 10.
- We use the Chinese Remainder Theorem (CRT) and check the sum modulo 2 and modulo 5.
- **Modulo 2**: The sum is `sum_{j | (j&N)==j} v_j` (mod 2), using the property that `C(N, j)` is odd iff `(j&N)==j`. This can be computed in O(N).
- **Modulo 5**: The sum is `sum_{j=0 to N} (C(N, j) mod 5) * v_j` (mod 5). We can compute `C(N, j) mod 5` for each `j` using Lucas's Theorem. This involves converting `N` and `j` to base 5, which takes `O(log j)` time for each `j`.
- The final result is `true` if both sums (mod 2 and mod 5) are zero.

## Optimized Combinatorial Formula with Fast Summation
This approach builds upon the combinatorial formula and optimizes the calculation of the weighted sum. The key bottleneck, which is the summation modulo 5, can be computed in linear time using an algorithm that resembles a Fast Walsh-Hadamard Transform. This method avoids the `log n` factor by processing digits in base 5 in a structured, iterative manner, leading to the most efficient solution.
**Time:** O(n). The modulo 2 check is `O(n)`. The `fastSumModP` function for modulo 5 has a total number of operations proportional to `n + n/5 + n/25 + ...`, which is a geometric series that sums to `O(n)`. Therefore, the overall time complexity is linear. · **Space:** O(n). The `fastSumModP` function requires an auxiliary array. The largest one is `O(n)` at the first step. The space can be optimized to `O(n)` by using two arrays and swapping pointers.
**Pros:** Optimal time complexity of `O(n)`.; Scales best for very large inputs.; Demonstrates a deep understanding of the problem's mathematical structure.
**Cons:** This is the most complex approach to understand and implement correctly.; The constant factors in the `O(n)` complexity might be larger than the `O(n log n)` approach for smaller `n`, but it scales much better.
### Explanation
We can optimize the `O(n log n)` approach to `O(n)`. The bottleneck is calculating `S_5 = sum_{j=0 to N} (C(N, j) mod 5) * v_j`. This sum can be computed in linear time.

Let `p=5`. The sum `S_p(N, data) = sum_{j=0 to N} (C(N, j) mod p) * data[j]` can be computed by an iterative algorithm. Let `d_0` be the initial data array `v`. We generate a sequence of arrays `d_1, d_2, ...` where `d_{r+1}` is computed from `d_r`. The size of `d_r` is `ceil(N/p^r)`. The recurrence is:
`d_{r+1}[i] = sum_{j=0 to N_r} C(N_r, j) * d_r[i*p + j] mod p`, where `N_r` is the `r`-th digit of `N` in base `p`.

This process is repeated `k = floor(log_p N)` times. The total number of operations is `sum_{r=0 to k} (N/p^{r+1}) * p = N * sum_{r=0 to k} 1/p^r`, which is `O(N)`. The final answer is the single element in the last array `d_{k+1}`.

```java
class Solution {
    public boolean checkEqual(String s) {
        int n = s.length();
        if (n <= 2) return s.charAt(0) == s.charAt(1);
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = s.charAt(i) - '0';
        }

        int N = n - 3;
        int[] v = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            v[i] = d[i + 2] - d[i];
        }

        // Check modulo 2
        int sumMod2 = 0;
        for (int j = 0; j <= N; j++) {
            if ((j & N) == j) {
                sumMod2 = (sumMod2 + v[j]) % 2;
            }
        }
        if ((sumMod2 + 2) % 2 != 0) return false;

        // Check modulo 5 with O(n) algorithm
        int sumMod5 = fastSumModP(N, v, 5);
        if ((sumMod5 + 5) % 5 != 0) return false;

        return true;
    }

    private int fastSumModP(int n, int[] data, int p) {
        int[][] C_p = new int[][]{{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}};
        int[] currentData = new int[data.length];
        for(int i=0; i<data.length; i++) {
            currentData[i] = (data[i] % p + p) % p;
        }

        int tempN = n;
        int currentLen = data.length;

        while (tempN > 0) {
            int np = tempN % p;
            int nextLen = (currentLen + p - 1) / p;
            int[] nextData = new int[nextLen];
            for (int i = 0; i < nextLen; i++) {
                long sum = 0;
                for (int j = 0; j <= np; j++) {
                    int idx = i * p + j;
                    if (idx < currentLen) {
                        sum = (sum + (long)C_p[np][j] * currentData[idx]) % p;
                    }
                }
                nextData[i] = (int)sum;
            }
            currentData = nextData;
            currentLen = nextLen;
            tempN /= p;
        }
        return currentData[0];
    }
}
```
### Algorithm
- The problem is reduced to computing `Sum = sum_{j=0 to N} C(N, j) * v_j` (mod 10), where `N=n-3` and `v_j = d_{j+2}-d_j`, same as the previous approach.
- The `O(n log n)` bottleneck was computing the sum modulo 5. This can be optimized to `O(n)`.
- The sum `S_5 = sum_{j=0 to N} (C(N, j) mod 5) * v_j` can be calculated using a fast transform-like method.
- Let `N` in base 5 be `N_k...N_0`. The sum can be expressed as a series of nested summations: `sum_{j_k=0..N_k} C(N_k,j_k) * ... * sum_{j_0=0..N_0} C(N_0,j_0) * v_{...}`.
- This can be computed iteratively. Start with `data = v`. In step `r` (from 0 to `k`), create a new array `newData` by combining elements of `data` separated by `5^r` distance, weighted by `C(N_r, j)`. 
- The size of the data array shrinks by a factor of 5 in each step. The total computation is `O(N + N/5 + N/25 + ...) = O(N)`.
- The modulo 2 check is already `O(N)`, so the total time complexity becomes `O(N)`.