Skip to main content
Talentd

Check If Digits Are Equal in String After Operations II - Solution & Explanation

HardMathStringCombinatoricsNumber Theory3 min readAsked at: ADP, Google
Practice this problem

Problem Statement

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.

Approach Overview

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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct SimulationO(n^2)O(n)Understanding the transformation process or when input size is very small
Combinatorics with Binomial Coefficients mod 10O(n)O(1)Large inputs where repeated simulation is too slow; optimal interview solution

Video Solution

3463 & 3461 Check If Digits Are Equal in String After Operations II | nCr | Luca's Theorem | Pascals • Aryan Mittal • 6,576 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Check If Digits Are Equal in String After Operations II easy or hard?
Check If Digits Are Equal in String After Operations II is classified as Hard. The challenge is recognizing that repeated pair operations form Pascal's Triangle and then handling binomial coefficients modulo a non-prime number (10) using number theory techniques.
Check If Digits Are Equal in String After Operations II Python/Java solution
Most implementations compute binomial coefficients modulo 10 while iterating through the string and accumulating two weighted sums. The same logic translates directly across Python, Java, C++, and Go because it only uses integer arithmetic and modular operations.
How to solve Check If Digits Are Equal in String After Operations II in O(n)?
Observe that repeated adjacent sums follow Pascal's Triangle. After n-2 operations, the final digits equal weighted sums of the original digits using coefficients C(n-2, i). Compute each coefficient modulo 10 using Lucas' theorem for mod 2 and mod 5, combine them with the Chinese Remainder method, and accumulate the two final sums in one pass.
What is the best approach for Check If Digits Are Equal in String After Operations II?
The optimal approach uses combinatorics. Repeated pair-sum operations form Pascal's Triangle coefficients, so the final digits can be expressed as weighted sums using C(n-2, i). Compute these binomial coefficients modulo 10 using Lucas' theorem with mod 2 and mod 5, then combine the results. This reduces the complexity to O(n) time and O(1) space.
Is Check If Digits Are Equal in String After Operations II asked at Google/Amazon/Meta?
Problems combining combinatorics, modular arithmetic, and string transformations commonly appear in interviews at companies like Google, Amazon, and Meta. The pattern-recognition aspect—reducing repeated operations to a binomial expansion—is a typical advanced interview expectation.
What data structure is used in Check If Digits Are Equal in String After Operations II?
The solution does not rely on complex data structures. It mainly uses arithmetic on digits and combinatorial coefficients. The key techniques come from number theory and combinatorics rather than arrays, trees, or hash maps.
What is the time complexity of Check If Digits Are Equal in String After Operations II?
The optimal combinatorial solution runs in O(n) time with O(1) extra space because it processes each digit once while computing binomial coefficients modulo 10. A naive simulation requires O(n^2) time since each operation rebuilds a slightly shorter string.

Ready to solve this problem?

Practice Check If Digits Are Equal in String After Operations II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Pascal's Triangle