Check If Digits Are Equal in String After Operations II

• 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.

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.

1class Solution {2    public boolean checkEqual(String s) {3        while (s.length() > 2) {4            StringBuilder next_s = new StringBuilder();5            for (int i = 0; i < s.length() - 1; i++) {6                int digit1 = s.charAt(i) - '0';7                int digit2 = s.charAt(i + 1) - '0';8                int sum = (digit1 + digit2) % 10;9                next_s.append(sum);10            }11            s = next_s.toString();12        }13        return s.charAt(0) == s.charAt(1);14    }15}

• 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.

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.

1class Solution {2    public boolean checkEqual(String s) {3        int n = s.length();4        if (n <= 2) return s.charAt(0) == s.charAt(1);5        int[] d = new int[n];6        for (int i = 0; i < n; i++) {7            d[i] = s.charAt(i) - '0';8        }9 10        int N = n - 3;11        int[] v = new int[N + 1];12        for (int i = 0; i <= N; i++) {13            v[i] = d[i + 2] - d[i];14        }15 16        // Check modulo 217        int sumMod2 = 0;18        for (int j = 0; j <= N; j++) {19            if ((j & N) == j) {20                sumMod2 = (sumMod2 + v[j]) % 2;21            }22        }23        if ((sumMod2 + 2) % 2 != 0) return false;24 25        // Check modulo 526        int sumMod5 = 0;27        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}};28        for (int j = 0; j <= N; j++) {29            long c5 = getCnkModP(N, j, 5, C_5);30            long term = (c5 * v[j]) % 5;31            sumMod5 = (int)((sumMod5 + term) % 5);32        }33        if ((sumMod5 + 5) % 5 != 0) return false;34 35        return true;36    }37 38    private long getCnkModP(int n, int k, int p, int[][] C_p) {39        if (k < 0 || k > n) return 0;40        long res = 1;41        while (n > 0) {42            int ni = n % p;43            int ki = k % p;44            if (ki > ni) return 0;45            res = (res * C_p[ni][ki]) % p;46            n /= p;47            k /= p;48        }49        return res;50    }51}

• 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).

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}.

1class Solution {2    public boolean checkEqual(String s) {3        int n = s.length();4        if (n <= 2) return s.charAt(0) == s.charAt(1);5        int[] d = new int[n];6        for (int i = 0; i < n; i++) {7            d[i] = s.charAt(i) - '0';8        }9 10        int N = n - 3;11        int[] v = new int[N + 1];12        for (int i = 0; i <= N; i++) {13            v[i] = d[i + 2] - d[i];14        }15 16        // Check modulo 217        int sumMod2 = 0;18        for (int j = 0; j <= N; j++) {19            if ((j & N) == j) {20                sumMod2 = (sumMod2 + v[j]) % 2;21            }22        }23        if ((sumMod2 + 2) % 2 != 0) return false;24 25        // Check modulo 5 with O(n) algorithm26        int sumMod5 = fastSumModP(N, v, 5);27        if ((sumMod5 + 5) % 5 != 0) return false;28 29        return true;30    }31 32    private int fastSumModP(int n, int[] data, int p) {33        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}};34        int[] currentData = new int[data.length];35        for(int i=0; i<data.length; i++) {36            currentData[i] = (data[i] % p + p) % p;37        }38 39        int tempN = n;40        int currentLen = data.length;41 42        while (tempN > 0) {43            int np = tempN % p;44            int nextLen = (currentLen + p - 1) / p;45            int[] nextData = new int[nextLen];46            for (int i = 0; i < nextLen; i++) {47                long sum = 0;48                for (int j = 0; j <= np; j++) {49                    int idx = i * p + j;50                    if (idx < currentLen) {51                        sum = (sum + (long)C_p[np][j] * currentData[idx]) % p;52                    }53                }54                nextData[i] = (int)sum;55            }56            currentData = nextData;57            currentLen = nextLen;58            tempN /= p;59        }60        return currentData[0];61    }62}