Check If Digits Are Equal in String After Operations I - Video Solutions
3463 & 3461 Check If Digits Are Equal in String After Operations II | nCr | Luca's Theorem | Pascals
Check If Digits Are Equal in String After Operations I - Video Solution
Watch 10 video solutions for Check If Digits Are Equal in String After Operations I, a easy level problem involving Math, String, Simulation. This walkthrough by Aryan Mittal has 6,576 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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
swith 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 = 2sbecomes"292"
- Second operation:
(s[0] + s[1]) % 10 = (2 + 9) % 10 = 1(s[1] + s[2]) % 10 = (9 + 2) % 10 = 1sbecomes"11"
- Since the digits in
"11"are the same, the output istrue.
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 isfalse.
Constraints:
3 <= s.length <= 100sconsists of only digits.
Approach Overview
Problem Overview: You get a string of digits. In one operation, replace every adjacent pair (a, b) with (a + b) % 10, forming a new string that is one character shorter. Repeat until only two digits remain. The task is to check whether those final two digits are equal.
Approach 1: Direct Simulation (O(n^2) time, O(n) space)
Store the digits in an array and repeatedly simulate the described operation. For each step, iterate through the current array and compute (digits[i] + digits[i+1]) % 10 for every adjacent pair, building the next array. Each iteration reduces the length by one, so the process runs roughly n + (n-1) + ... + 2 operations. The logic mirrors the problem statement exactly, which makes it easy to reason about and implement. This approach fits naturally with string processing and simulation techniques.
Approach 2: In‑Place Simulation (O(n^2) time, O(1) space)
You can avoid allocating a new array at every step. Convert the string into a mutable list of digits and reuse the same array. During each round, iterate from left to right and overwrite digits[i] with (digits[i] + digits[i+1]) % 10. After finishing a pass, treat the effective length as one smaller. The computation still performs the same number of arithmetic operations, but memory usage drops to constant space because the transformation happens in place. This technique is common when implementing iterative transformations on arrays or strings.
The math behind the repeated reductions forms a triangular pattern similar to Pascal's triangle, which connects to math and combinatorial reasoning. However, for this version of the problem the constraints are small enough that straightforward simulation is the simplest and most practical solution.
Recommended for interviews: The in-place simulation is typically preferred. It demonstrates that you understand the transformation process and can optimize memory usage while keeping the logic clear. Starting with the basic simulation also shows solid problem‑solving steps before refining the implementation.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation with New Array | O(n^2) | O(n) | Best for clarity and quick implementation that follows the problem statement step by step |
| In‑Place Simulation | O(n^2) | O(1) | When you want the same logic but with constant extra memory |