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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

1
2
3
4
5
6
7
8

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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)