LeetCode 3463 - Check If Digits Are Equal in String After Operations II

The problem asks us to repeatedly transform a string of digits until only two digits remain, and then check if those two digits are the same. The transformation involves taking each consecutive pair of digits, summing them, and taking the result modulo 10 to form a new digit.

leetcodehardmathstringcombinatoricsnumber-theory

LeetCode Problem 3463

Difficulty: 🔴 Hard
Topics: Math, String, Combinatorics, Number Theory

Solution

Problem Understanding

The problem asks us to repeatedly transform a string of digits until only two digits remain, and then check if those two digits are the same. The transformation involves taking each consecutive pair of digits, summing them, and taking the result modulo 10 to form a new digit. This process is applied repeatedly, replacing the string with the new sequence, until the string length is exactly two. The input s is guaranteed to be a string of digits with a length between 3 and 105. The output is a boolean value indicating whether the final two digits are equal.

The key constraints imply that a naive approach simulating each transformation step by step may become too slow for large strings, since the string can have up to 105 characters, and each operation reduces the length by only one. Edge cases include strings where all digits are the same, strings that result in repeated patterns, and strings with maximum length to test performance.

Approaches

Brute Force

The brute-force approach directly simulates the transformation process. For each iteration, it computes the new string of digits by summing consecutive pairs modulo 10. This continues until only two digits remain. This method is correct because it follows the rules exactly. However, it is inefficient for long strings because the string is reduced by only one character per operation, leading to a total of approximately O(n²) operations for a string of length n.

Optimal Approach

The key insight for an optimal solution is that the transformation is essentially a combinatorial process that can be represented using binomial coefficients modulo 10. For any final digit in the two-digit result, it is the sum of the contributions of the original digits multiplied by specific binomial coefficients. Specifically, for a string of length n, the two final digits are:

  • First final digit: sum of (s[i] * C(n-2, i)) % 10 for all i in 0..n-2
  • Second final digit: sum of (s[i+1] * C(n-2, i)) % 10 for all i in 0..n-2

This approach avoids repeated transformations and computes the result in O(n²) in theory, but modulo 10 arithmetic allows for optimizations that reduce constant factors.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Simulates each operation until two digits remain
Optimal O(n²) O(n) Uses combinatorial binomial coefficients modulo 10 to compute final digits directly

Algorithm Walkthrough

  1. Parse the string s into an array of digits.
  2. Compute the first and second final digits using the binomial coefficient method modulo 10. For the first digit, consider contributions from positions 0 to n-2; for the second digit, consider contributions from positions 1 to n-1.
  3. Use a combinatorial formula with modular arithmetic to avoid large integer computations.
  4. Compare the two computed digits. If they are equal, return true; otherwise, return false.

Why it works: The transformation process is linear in terms of the original digits modulo 10. By analyzing the contribution of each original digit to the final two digits using combinatorial coefficients, we can compute the final result without simulating each intermediate string.

Python Solution

from math import comb

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        n = len(s)
        digits = [int(c) for c in s]
        
        first_digit = sum(digits[i] * comb(n - 2, i) for i in range(n - 1)) % 10
        second_digit = sum(digits[i + 1] * comb(n - 2, i) for i in range(n - 1)) % 10
        
        return first_digit == second_digit

The Python implementation converts the string to a list of digits. It then calculates the first and second final digits using the binomial coefficient formula. The modulo 10 operation ensures the calculation remains within single-digit bounds. Finally, it checks if the two digits are equal.

Go Solution

package main

import "math/big"

func comb(n, k int) int64 {
    return big.NewInt(0).Binomial(int64(n), int64(k)).Int64()
}

func hasSameDigits(s string) bool {
    n := len(s)
    digits := make([]int, n)
    for i := 0; i < n; i++ {
        digits[i] = int(s[i] - '0')
    }
    
    var firstDigit, secondDigit int
    for i := 0; i < n-1; i++ {
        c := int(comb(n-2, i) % 10)
        firstDigit = (firstDigit + digits[i]*c) % 10
        secondDigit = (secondDigit + digits[i+1]*c) % 10
    }
    
    return firstDigit == secondDigit
}

The Go implementation handles binomial coefficients using the math/big package to avoid integer overflow. It calculates each final digit modulo 10 and checks if they are equal. Unlike Python, Go requires explicit conversion between integer types for combinatorial calculations.

Worked Examples

Example 1: s = "3902"

Step String Computation
Initial 3902 -
Operation 1 292 (3+9)%10=2, (9+0)%10=9, (0+2)%10=2
Operation 2 11 (2+9)%10=1, (9+2)%10=1
Final 11 1 == 1 → true

Example 2: s = "34789"

Step String Computation
Initial 34789 -
Operation 1 7157 (3+4)%10=7, (4+7)%10=1, (7+8)%10=5, (8+9)%10=7
Operation 2 862 (7+1)%10=8, (1+5)%10=6, (5+7)%10=2
Operation 3 48 (8+6)%10=4, (6+2)%10=8
Final 48 4 != 8 → false

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Each of n digits may contribute to binomial sums for n-1 positions
Space O(n) Storage for digit array

The combinatorial calculation avoids repeated string construction, but modulo arithmetic prevents integer overflow and keeps operations efficient.

Test Cases

# Provided examples
assert Solution().hasSameDigits("3902") == True  # final digits are 11
assert Solution().hasSameDigits("34789") == False  # final digits are 48

# Edge cases
assert Solution().hasSameDigits("111") == True  # all same digits, final is 11
assert Solution().hasSameDigits("123") == False  # final digits 35
assert Solution().hasSameDigits("999999") == True  # repeated digits, final digits same
assert Solution().hasSameDigits("1020304050") == False  # alternating digits, final digits different

# Large input
assert Solution().hasSameDigits("1"*105) == True  # large input with all ones
Test Why
"3902" Checks standard example with repeated operations
"34789" Checks multiple steps with unequal final digits
"111" Minimal input with all equal digits
"123" Small string with unequal final digits
"999999" Repeated digits to test combination arithmetic
"1020304050" Alternating digits pattern to test modulo logic
"1"*105 Maximum size input to test performance

Edge Cases

One edge case is when all digits in the string are identical, e.g., "111...". Here, every operation produces the same intermediate digit, guaranteeing that the final two digits are equal. Another edge case is alternating digits that produce patterns that eventually differ, such as "102030". This could trip up implementations that assume repeated patterns lead to equal digits. Finally, the maximum length input tests performance and memory usage, ensuring that the combinatorial approach does not overflow or take excessive time. All of these cases are correctly handled by computing contributions using binomial coefficients modulo 10.