Problem Description

You are given a string s that contains only digits. Your task is to repeatedly perform a specific operation on this string until it has exactly two digits remaining.

The operation works as follows:

• Starting from the first digit, look at each pair of consecutive digits in the string
• For each pair, calculate the sum of the two digits and take the result modulo 10 (this gives you the last digit of the sum)
• Create a new string using all these calculated digits in the order they were computed
• Replace the original string with this new string

You keep repeating this process until the string is reduced to exactly two digits.

Once you have exactly two digits remaining, return true if both digits are the same, and false otherwise.

For example, if you start with "123":

• First iteration: pairs are (1,2) and (2,3), giving us (1+2)%10 = 3 and (2+3)%10 = 5, resulting in "35"
• The string now has 2 digits, so we stop
• Since 3 ≠ 5, we return false

The solution uses a clever approach with nested loops. The outer loop controls how many iterations are needed (from n-1 down to 2), while the inner loop performs the modulo sum operation on consecutive pairs. By working directly with the array and updating values in place, it efficiently reduces the string to two digits and then compares them.

Intuition

The key insight is recognizing that each iteration reduces the number of digits by exactly 1. If we start with n digits, after one iteration we'll have n-1 digits, after two iterations we'll have n-2 digits, and so on. This means we need exactly n-2 iterations to reduce an n-digit string down to 2 digits.

Rather than creating a new array or string for each iteration, we can optimize by reusing the same array. The pattern becomes clear when we visualize what happens:

• In the first iteration, we compute n-1 new values from n original values
• In the second iteration, we compute n-2 new values from the n-1 values we just calculated
• This continues until we have just 2 values left

The clever part is realizing we can overwrite the array from left to right during each iteration. When computing t[i] = (t[i] + t[i+1]) % 10, we're done using the original value of t[i], so we can safely replace it with the new value. This in-place modification saves space and simplifies the code.

The outer loop for k in range(n-1, 1, -1) controls how many values we compute in each iteration - starting with n-1 pairs in the first iteration, then n-2 pairs in the second, and so on. The inner loop for i in range(k) performs the actual computation for each pair in that iteration.

After all iterations complete, the first two positions of our array contain the final two digits, so we simply check if t[0] == t[1] to determine our answer.

Learn more about Math and Combinatorics patterns.

Solution Approach

The solution implements a simulation approach that directly manipulates the input string as a list of integers. Here's how the implementation works:

First, we convert the string s into a list of integers: t = list(map(int, s)). This allows us to work with numerical values directly rather than converting characters repeatedly.

We store the length n = len(t) to determine how many iterations we need to perform.

The core logic uses nested loops:

• The outer loop for k in range(n - 1, 1, -1): controls the number of iterations. It starts from n-1 and counts down to 2. The variable k represents how many new digits we'll compute in each iteration.
• The inner loop for i in range(k): iterates through each position where we need to compute a new digit.

In each inner loop iteration, we perform the key operation: t[i] = (t[i] + t[i + 1]) % 10. This:

1. Takes the current digit at position i and the next digit at position i+1
2. Adds them together
3. Takes the result modulo 10 to get the last digit
4. Stores this new value back at position i

The beauty of this approach is that we're reusing the same array throughout all iterations. After the first iteration, positions 0 through n-2 contain our new values, and we ignore position n-1. After the second iteration, positions 0 through n-3 contain the newer values, and so on.

When both loops complete, we're guaranteed to have exactly 2 digits stored in positions t[0] and t[1]. We simply return t[0] == t[1] to check if they're the same.

The time complexity is O(n²) where n is the length of the input string, as we perform roughly (n-1) + (n-2) + ... + 2 operations total. The space complexity is O(n) for storing the list of digits.

Example Walkthrough

Let's walk through the solution with the string s = "4321".

Initial Setup:

• Convert string to integer list: t = [4, 3, 2, 1]
• Length n = 4
• We need n-2 = 2 iterations to reduce to 2 digits

First Iteration (k = 3):

• We compute 3 new values (indices 0, 1, 2)
• i = 0: t[0] = (4 + 3) % 10 = 7 → t = [7, 3, 2, 1]
• i = 1: t[1] = (3 + 2) % 10 = 5 → t = [7, 5, 2, 1]
• i = 2: t[2] = (2 + 1) % 10 = 3 → t = [7, 5, 3, 1]
• After this iteration, we have 3 valid digits: [7, 5, 3] (ignore index 3)

Second Iteration (k = 2):

• We compute 2 new values (indices 0, 1)
• i = 0: t[0] = (7 + 5) % 10 = 2 → t = [2, 5, 3, 1]
• i = 1: t[1] = (5 + 3) % 10 = 8 → t = [2, 8, 3, 1]
• After this iteration, we have 2 valid digits: [2, 8] (ignore indices 2 and 3)

Final Check:

• Compare t[0] and t[1]: 2 ≠ 8
• Return false

The key insight is how we reuse the same array throughout, only caring about the first k positions in each iteration, where k decreases by 1 each time. This eliminates the need to create new arrays and makes the solution both space and implementation efficient.

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), where n is the length of the string s. This is because we have two nested loops: the outer loop runs from n-1 down to 2 (approximately n-2 iterations), and for each iteration k, the inner loop runs k times. The total number of operations is approximately (n-1) + (n-2) + ... + 2 = (n-1) * (n-2) / 2, which simplifies to O(n^2).

The space complexity is O(n), where n is the length of the string s. This is due to the conversion of the string to a list of integers t = list(map(int, s)), which creates a new list of size n. The algorithm then modifies this list in-place without using any additional space that scales with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Loop Boundaries

The Pitfall: A common mistake is incorrectly setting the loop boundaries, particularly in the outer loop. Developers might write:

• range(n, 1, -1) instead of range(n-1, 1, -1) - This would cause an index out of bounds error
• range(n-1, 0, -1) instead of range(n-1, 1, -1) - This would perform one extra unnecessary iteration

Why it happens: The confusion arises from not clearly understanding that in each iteration, we're computing k new values from k+1 existing values. When we have n digits initially, we can only compute n-1 new values.

Solution: Remember that:

• The outer loop variable k represents the number of new digits we're computing
• We start with n digits, so we can compute at most n-1 new values
• We stop when k=2 (not k=1) because we need exactly 2 digits remaining

2. Modifying the Wrong Data Structure

The Pitfall: Creating a new list for each iteration instead of modifying in-place:

for k in range(n - 1, 1, -1):
    new_digits = []  # Creating new list each time
    for i in range(k):
        new_digits.append((digits[i] + digits[i + 1]) % 10)
    digits = new_digits  # Reassigning

Why it happens: This approach seems more intuitive but is less efficient and can lead to errors if the indexing isn't adjusted properly for the shrinking list size.

Solution: Stick with in-place modification. The original approach cleverly reuses the same array, only updating the positions that matter for the next iteration.

3. Forgetting the Modulo Operation

The Pitfall: Writing digits[i] = digits[i] + digits[i + 1] without the % 10 operation.

Why it happens: The problem description mentions "sum of two digits" which might lead developers to forget that we only want the last digit of the sum.

Solution: Always include % 10 to ensure we're storing only single digits. For example, if we have digits 7 and 8, their sum is 15, but we want to store 5 (15 % 10 = 5).

4. Incorrect Final Comparison

The Pitfall: Accessing the wrong indices for the final comparison, such as:

• return digits[0] == digits[n-1] - This would compare with an outdated value
• return digits[1] == digits[2] - Wrong indices entirely

Why it happens: After all the iterations, it's easy to lose track of where the final two values are stored.

Solution: The final two values are always at indices 0 and 1 after the reduction process completes. The algorithm overwrites the array from left to right, so digits[0] and digits[1] contain our final result.