Check If Digits Are Equal in String After Operations II
HardPrompt
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 <= 105sconsists of only digits.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Start a loop that continues as long as the length of the string
sis greater than 2. - Inside the loop, create a new
StringBuilderto build the string for the next iteration. - Iterate through the current string
sfrom the first character up to the second-to-last character. - For each index
i, parse the digits ats[i]ands[i+1], calculate their sum modulo 10. - Append the resulting digit to the
StringBuilder. - After the inner loop, replace
swith the string generated by theStringBuilder. - Once the loop terminates (when
shas a length of 2), compare the two characters ofs. - Return
trueif they are equal, andfalseotherwise.
Walkthrough
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.
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); }}Complexity
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.
Trade-offs
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.lengthup to 10^5). This will lead to a 'Time Limit Exceeded' (TLE) error on large inputs.
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.