problemhardalgorithmsleetcode-3463leetcode 3463leetcode3463

Check If Digits Are Equal in String After Operations II

HardUpdated: Jul 7, 2025
Practice on:
LeetCode

Problem

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 s with 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.

Examples

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 = 2`
* `s` becomes `"292"`
* Second operation: 
* `(s[0] + s[1]) % 10 = (2 + 9) % 10 = 1`
* `(s[1] + s[2]) % 10 = (9 + 2) % 10 = 1`
* `s` becomes `"11"`
* Since the digits in `"11"` are the same, the output is `true`.

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 is `false`.

Constraints

  • 3 <= s.length <= 10^5
  • s consists of only digits.

Solution

Method 1 – Combinatorial Coefficient Simulation

Intuition

After repeatedly applying the operation, the final two digits can be expressed as a linear combination of the original digits, with coefficients determined by binomial coefficients modulo 10. We can precompute these coefficients and use them to compute the final two digits efficiently, even for large strings.

Approach

  1. Let n be the length of the string.
  2. The final two digits can be written as:
    • left = sum_{i=0}^{n-1} C(n-2, i) * s[i] (mod 10)
    • right = sum_{i=0}^{n-1} C(n-2, i-1) * s[i] (mod 10) where C(n, k) is the binomial coefficient, and C(n, k) = 0 if k < 0 or k > n.
  3. Precompute binomial coefficients modulo 10 for all needed values.
  4. Compute left and right as above.
  5. Return true if left == right, else false.

Code

C++
class Solution {
public:
    bool isEqual(string s) {
        int n = s.size();
        vector<int> arr(n);
        for (int i = 0; i < n; ++i) arr[i] = s[i] - '0';
        vector<int> C(n, 1);
        for (int i = 1; i < n-1; ++i) C[i] = (1LL * C[i-1] * (n-2-i+1) / i) % 10;
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            int c1 = (i <= n-2) ? C[i] : 0;
            int c2 = (i-1 >= 0 && i-1 <= n-2) ? C[i-1] : 0;
            l = (l + c1 * arr[i]) % 10;
            r = (r + c2 * arr[i]) % 10;
        }
        return l == r;
    }
};
Java
class Solution {
    public boolean isEqual(String s) {
        int n = s.length();
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) arr[i] = s.charAt(i) - '0';
        int[] C = new int[n];
        C[0] = 1;
        for (int i = 1; i < n-1; ++i) C[i] = (int)((long)C[i-1] * (n-2-i+1) / i % 10);
        int l = 0, r = 0;
        for (int i = 0; i < n; ++i) {
            int c1 = (i <= n-2) ? C[i] : 0;
            int c2 = (i-1 >= 0 && i-1 <= n-2) ? C[i-1] : 0;
            l = (l + c1 * arr[i]) % 10;
            r = (r + c2 * arr[i]) % 10;
        }
        return l == r;
    }
}
Python
class Solution:
    def isEqual(self, s: str) -> bool:
        n = len(s)
        arr = [int(c) for c in s]
        C = [1] * n
        for i in range(1, n-1):
            C[i] = (C[i-1] * (n-2-i+1) // i) % 10
        l = r = 0
        for i in range(n):
            c1 = C[i] if i <= n-2 else 0
            c2 = C[i-1] if 0 <= i-1 <= n-2 else 0
            l = (l + c1 * arr[i]) % 10
            r = (r + c2 * arr[i]) % 10
        return l == r
Go
func isEqual(s string) bool {
    n := len(s)
    arr := make([]int, n)
    for i := range s {
        arr[i] = int(s[i] - '0')
    }
    C := make([]int, n)
    C[0] = 1
    for i := 1; i < n-1; i++ {
        C[i] = (C[i-1] * (n-2-i+1) / i) % 10
    }
    l, r := 0, 0
    for i := 0; i < n; i++ {
        c1 := 0
        if i <= n-2 {
            c1 = C[i]
        }
        c2 := 0
        if i-1 >= 0 && i-1 <= n-2 {
            c2 = C[i-1]
        }
        l = (l + c1*arr[i]) % 10
        r = (r + c2*arr[i]) % 10
    }
    return l == r
}
Kotlin
class Solution {
    fun isEqual(s: String): Boolean {
        val n = s.length
        val arr = s.map { it - '0' }
        val C = IntArray(n) { 1 }
        for (i in 1 until n-1) C[i] = (C[i-1] * (n-2-i+1) / i) % 10
        var l = 0; var r = 0
        for (i in 0 until n) {
            val c1 = if (i <= n-2) C[i] else 0
            val c2 = if (i-1 in 0..(n-2)) C[i-1] else 0
            l = (l + c1 * arr[i]) % 10
            r = (r + c2 * arr[i]) % 10
        }
        return l == r
    }
}
Rust
impl Solution {
    pub fn is_equal(s: String) -> bool {
        let n = s.len();
        let arr: Vec<u8> = s.bytes().map(|b| b - b'0').collect();
        let mut c = vec![1u64; n];
        for i in 1..n-1 {
            c[i] = c[i-1] * (n as u64 - 2 - i as u64 + 1) / i as u64 % 10;
        }
        let (mut l, mut r) = (0u64, 0u64);
        for i in 0..n {
            let c1 = if i <= n-2 { c[i] } else { 0 };
            let c2 = if i > 0 && i-1 <= n-2 { c[i-1] } else { 0 };
            l = (l + c1 * arr[i] as u64) % 10;
            r = (r + c2 * arr[i] as u64) % 10;
        }
        l == r
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string.
  • 🧺 Space complexity: O(n)

Comments