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 <= 100
  • s consists of only digits.

Solution

Method 1 – Simulation

Intuition

We repeatedly reduce the string by replacing each pair of consecutive digits with their sum modulo 10, until only two digits remain. If the final two digits are equal, return true; otherwise, return false. This is a direct simulation of the process described in the problem.

Approach

  1. Convert the string to a list of integers.
  2. While the length of the list is greater than 2:
    • For each pair of consecutive digits, compute their sum modulo 10 and build a new list.
    • Replace the current list with the new list.
  3. After the loop, check if the two remaining digits are equal.
  4. Return true if they are equal, otherwise false.

Code

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

class Solution {
public:
    bool isEqual(string s) {
        vector<int> arr;
        for (char c : s) arr.push_back(c - '0');
        while (arr.size() > 2) {
            vector<int> nxt;
            for (int i = 0; i + 1 < arr.size(); ++i) {
                nxt.push_back((arr[i] + arr[i+1]) % 10);
            }
            arr = nxt;
        }
        return arr[0] == arr[1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func isEqual(s string) bool {
    arr := make([]int, len(s))
    for i := range s {
        arr[i] = int(s[i] - '0')
    }
    for len(arr) > 2 {
        nxt := make([]int, len(arr)-1)
        for i := 0; i+1 < len(arr); i++ {
            nxt[i] = (arr[i] + arr[i+1]) % 10
        }
        arr = nxt
    }
    return arr[0] == arr[1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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';
        while (n > 2) {
            int[] nxt = new int[n-1];
            for (int i = 0; i+1 < n; ++i) nxt[i] = (arr[i] + arr[i+1]) % 10;
            arr = nxt;
            n--;
        }
        return arr[0] == arr[1];
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun isEqual(s: String): Boolean {
        var arr = s.map { it - '0' }
        while (arr.size > 2) {
            arr = arr.zipWithNext { a, b -> (a + b) % 10 }
        }
        return arr[0] == arr[1]
    }
}
1
2
3
4
5
6

class Solution:
    def isEqual(self, s: str) -> bool:
        arr = [int(c) for c in s]
        while len(arr) > 2:
            arr = [(arr[i] + arr[i+1]) % 10 for i in range(len(arr)-1)]
        return arr[0] == arr[1]
1
2
3
4
5
6
7
8
9

impl Solution {
    pub fn is_equal(s: String) -> bool {
        let mut arr: Vec<u8> = s.bytes().map(|b| b - b'0').collect();
        while arr.len() > 2 {
            arr = arr.windows(2).map(|w| (w[0] + w[1]) % 10).collect();
        }
        arr[0] == arr[1]
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of the string (since each round reduces the length by 1).
  • 🧺 Space complexity: O(n)