Check If Digits Are Equal in String After Operations II - Video Solutions

Problem Overview: You start with a numeric string. In each operation, replace the string with a new one where every position becomes (s[i] + s[i+1]) % 10. Repeat until only two digits remain. The task is to check whether those final two digits are equal.

Approach 1: Direct Simulation (Brute Force) (Time: O(n^2), Space: O(n))

The most straightforward solution literally simulates the process. Build the next string by iterating through adjacent pairs and computing (digit[i] + digit[i+1]) % 10. Each operation reduces the length by one, so a string of length n requires n-2 rounds. Since each round processes almost the entire string, the total work becomes quadratic. This approach works for small inputs and helps verify the transformation pattern, but it quickly becomes too slow for large n.

Approach 2: Combinatorics with Binomial Coefficients mod 10 (Optimal) (Time: O(n), Space: O(1))

The repeated pair-sum operation forms a structure identical to Pascal's Triangle. After k reductions, each digit becomes a weighted sum of original digits using binomial coefficients. After n-2 operations, the final two digits are linear combinations of the original digits:

A = sum(C(n-2, i) * s[i]) mod 10
B = sum(C(n-2, i) * s[i+1]) mod 10

The problem reduces to computing binomial coefficients C(n-2, i) modulo 10. Since 10 is not prime, standard modular combinatorics does not apply directly. Split the computation into mod 2 and mod 5 using Lucas' theorem, then combine the results with the Chinese Remainder principle. Iterate once through the string, compute each coefficient modulo 10, and accumulate the two sums.

This transforms the problem from repeatedly rebuilding strings into a single linear pass with combinatorial weights. The approach relies heavily on concepts from combinatorics, number theory, and careful modular arithmetic over a math-driven observation.

Recommended for interviews: Start by explaining the brute force simulation because it demonstrates how the operation works. Then derive the Pascal triangle pattern and move to the combinatorial formulation. Interviewers expect the optimized binomial-coefficient solution since it reduces the complexity from O(n^2) to O(n) and shows strong pattern recognition and modular arithmetic skills.