LeetCode 3461 - Check If Digits Are Equal in String After Operations I

This problem asks us to repeatedly transform a string of digits by summing consecutive pairs modulo 10, until only two digits remain, and then check whether those two digits are equal.

leetcodeeasymathstringsimulationcombinatoricsnumber-theory

LeetCode Problem 3461

Difficulty: 🟢 Easy
Topics: Math, String, Simulation, Combinatorics, Number Theory

Solution

Problem Understanding

This problem asks us to repeatedly transform a string of digits by summing consecutive pairs modulo 10, until only two digits remain, and then check whether those two digits are equal. In other words, we start with a string s of length at least 3 and, at each step, generate a new string where each element is (s[i] + s[i+1]) % 10. This continues until the string length becomes exactly 2. The expected output is a boolean: true if the final two digits are identical, false otherwise.

The input string s is guaranteed to consist only of digits, and its length ranges from 3 to 100. This range is small enough that simulating the process directly is feasible. Important edge cases include strings where all digits are the same, strings where the sum modulo 10 generates repeated values early, and strings that reduce to two digits that are different.

Approaches

A brute-force approach simply implements the transformation step by step. Starting with the initial string, we calculate (s[i] + s[i+1]) % 10 for each consecutive pair, replace s with the resulting sequence, and repeat until the string length is 2. This approach is correct because it directly follows the problem statement, but it repeatedly creates new strings and may require multiple iterations.

An optimal approach still follows the same process because the problem constraints are small. The only optimization is to avoid creating a new string for each transformation by using an in-place approach with arrays or lists, which reduces memory allocations but does not change the asymptotic complexity. The key observation is that since the maximum length is 100, the simulation will complete in a manageable number of steps.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Direct simulation of operations until length reduces to 2
Optimal O(n^2) O(n) Same as brute-force but can use in-place arrays to avoid repeated allocations

Algorithm Walkthrough

  1. Convert the input string s into a list of integers. This allows arithmetic operations directly on digits.

  2. While the length of the list is greater than 2, perform a transformation:

  3. Initialize a new empty list to store the next sequence of digits.

  4. Iterate over consecutive pairs in the current list. For each pair (a, b), compute (a + b) % 10 and append it to the new list.

  5. Replace the current list with the new list.

  6. After the loop ends, the list will have exactly two digits. Compare these two digits.

  7. Return true if they are equal, otherwise false.

Why it works: The algorithm faithfully simulates the operation defined in the problem. Each transformation reduces the length of the string by 1, ensuring that eventually we reach a string of length 2. By comparing the final two digits, we correctly determine whether they are identical.

Python Solution

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        # Convert the string to a list of integers for easy manipulation
        digits = [int(char) for char in s]
        
        # Repeat the transformation until only two digits remain
        while len(digits) > 2:
            next_digits = [(digits[i] + digits[i+1]) % 10 for i in range(len(digits) - 1)]
            digits = next_digits
        
        # Check if the final two digits are the same
        return digits[0] == digits[1]

The Python implementation starts by converting the string into integers. The while loop executes until only two digits remain. Within the loop, we generate a new list by summing consecutive digits modulo 10. After the loop, the two remaining digits are compared for equality.

Go Solution

func hasSameDigits(s string) bool {
    // Convert string to slice of integers
    digits := make([]int, len(s))
    for i, ch := range s {
        digits[i] = int(ch - '0')
    }
    
    // Repeat the transformation until only two digits remain
    for len(digits) > 2 {
        nextDigits := make([]int, len(digits)-1)
        for i := 0; i < len(digits)-1; i++ {
            nextDigits[i] = (digits[i] + digits[i+1]) % 10
        }
        digits = nextDigits
    }
    
    // Check if the final two digits are the same
    return digits[0] == digits[1]
}

In Go, the string is converted to a slice of integers. The transformation loop creates a new slice for each iteration, since slices are easier to manage than modifying in place. The comparison of the final two digits yields the correct boolean result.

Worked Examples

Example 1: s = "3902"

Step Digits
Initial [3, 9, 0, 2]
Transform 1 [(3+9)%10, (9+0)%10, (0+2)%10] → [2, 9, 2]
Transform 2 [(2+9)%10, (9+2)%10] → [1, 1]
Final 1 == 1 → true

Example 2: s = "34789"

Step Digits
Initial [3, 4, 7, 8, 9]
Transform 1 [7, 1, 5, 7]
Transform 2 [8, 6, 2]
Transform 3 [4, 8]
Final 4 != 8 → false

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Each transformation reduces the length by 1, and each step iterates over the current length, resulting in O(n + (n-1) + ... + 1) = O(n^2)
Space O(n) We store the current and next digit sequences in lists/slices of size at most n

The reasoning behind O(n^2) time is that the series of operations resembles a triangular sum: n + (n-1) + ... + 1 = n(n+1)/2.

Test Cases

# Provided examples
assert Solution().hasSameDigits("3902") == True  # transforms to "11"
assert Solution().hasSameDigits("34789") == False  # transforms to "48"

# Boundary cases
assert Solution().hasSameDigits("111") == True  # 1+1=2, 1+1=2, then 2 2
assert Solution().hasSameDigits("123") == False  # 1+2=3, 2+3=5, final 3 5
assert Solution().hasSameDigits("99999") == True  # multiple 9s, results in 8 8 eventually

# Stress case
assert Solution().hasSameDigits("0123456789") == False
Test Why
"3902" Example where final digits match
"34789" Example where final digits differ
"111" All digits identical, should return true
"123" Simple ascending sequence, should return false
"99999" High digits, tests modulo behavior
"0123456789" Longer string, tests multiple iterations

Edge Cases

One important edge case is when all digits in the string are the same. In this case, each transformation will generate repeated digits modulo 10, and the final two digits will also be identical. A naive implementation might mismanage modulo arithmetic, but our approach handles it correctly.

Another edge case is when the string contains zeros. Adding zeros modulo 10 can affect the sequence differently than expected. For instance, "102" transforms to "1 2" → false, which is correctly handled because we explicitly perform modulo 10 on every sum.

A final edge case is the maximum allowed string length of 100. Since each step reduces the length by 1, there are at most 98 transformations. The implementation handles this efficiently without performance issues because of the modest input size.