We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check If Digits Are Equal in String After Operations II

Number: 3774

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given a string s consisting of digits, you perform the following operation repeatedly until the string has exactly two digits:

  1. For every pair of consecutive digits (from left to right), compute (digit[i] + digit[i+1]) mod 10.
  2. Replace the string with the sequence of these newly computed digits (preserving their order).

Return true if the final two digits are the same, and false otherwise.

Key Insights

  • The process of repeatedly taking adjacent pair sums modulo 10 is linear. In fact, after k rounds the digit at a given position is a linear combination of some contiguous block of the original digits with coefficients given by binomial coefficients.
  • When the process stops (when exactly two digits remain), both final digits are weighted sums (modulo 10) of the original digits. Their coefficients come from successive rows of Pascal’s Triangle.
  • With some algebra it can be shown that the equality of the two final digits reduces to checking whether a certain telescoping sum of differences (each multiplied by a binomial coefficient) is 0 modulo 10.
  • By writing the final two numbers in a closed‐form the condition becomes: For r = s.length – 2, let final_first = ∑[j=0 to r] (C(r, j) * s[j]) mod 10 final_second = ∑[j=0 to r] (C(r, j) * s[j+1]) mod 10. Their equality is equivalent to ∑[j=0 to r] (C(r, j) * (s[j] – s[j+1])) ≡ 0 (mod 10).
  • Thus, instead of simulating the process which would be too slow for large s, we can directly compute the weighted difference in O(n) time by iterating over the digits and updating the binomial coefficient in a multiplicative fashion (taking care to perform exact division because the update formula for the binomial coefficient is exact).

Space and Time Complexity

Time Complexity: O(n), where n is the length of s, since we iterate once over the digits. Space Complexity: O(1) beyond the space used for s (only a few integer variables are maintained).

Solution

We note that if we denote the length of s by n and set r = n – 2, then it can be shown that the first final digit is   ∑[j=0 to r] (C(r, j) * s[j]) mod 10, and the second is   ∑[j=0 to r] (C(r, j) * s[j+1]) mod 10. Thus, the two numbers are equal if   ∑[j=0 to r] (C(r, j) * (s[j] – s[j+1])) ≡ 0 (mod 10).

We can compute this sum in one pass by iterating from j = 0 to r. In doing so, we update the binomial coefficient C(r, j) iteratively using the relation:   C(r, 0) = 1,   C(r, j+1) = C(r, j) * (r – j) / (j + 1). Since the division is exact (the binomial coefficient is an integer), we update the coefficient exactly and then take the result modulo 10. Finally, if the overall sum mod 10 is 0, the two digits will be equal.

For clarity and to cover multiple languages, we provide code solutions with clear line-by-line comments.

Code Solutions

# Python solution
def checkEqual(s: str) -> bool:
    n = len(s)
    # Convert the string to a list of integer digits.
    digits = [int(ch) for ch in s]
    r = n - 2  # The number of operations done is n-2.
    total = 0  # This will accumulate the weighted difference mod 10.
    binom = 1  # Starting with C(r, 0) = 1.
    
    # Iterate over j from 0 to r (inclusive).
    for j in range(r + 1):
        # Compute contribution: binom * (digit[j] - digit[j+1])
        total = (total + binom * (digits[j] - digits[j+1])) % 10
        # Update the binomial coefficient for next j if possible.
        if j < r:
            # Use the recurrence: C(r, j+1) = C(r, j) * (r - j) // (j + 1)
            binom = (binom * (r - j)) // (j + 1)
            # We only care about mod 10.
            binom %= 10
    # The final two digits are equal if the weighted difference is 0 modulo 10.
    return total % 10 == 0

# Example usage:
print(checkEqual("3902"))  # Expected: True
print(checkEqual("34789"))  # Expected: False
← Back to All Questions