# Check If Digits Are Equal in String After Operations I
**Difficulty:** EASY
[External](https://leetcode.com/problems/check-if-digits-are-equal-in-string-after-operations-i)
Canonical: https://scaleengineer.com/dsa/problems/check-if-digits-are-equal-in-string-after-operations-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** String
---
## 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`.

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

# Approaches
## Direct Simulation with String Manipulation
This approach directly simulates the process described in the problem statement. We start with the initial string and repeatedly apply the transformation rule, generating a new, shorter string in each step. This continues until the string's length is reduced to exactly two. Finally, we check if the two digits in the resulting string are equal.
**Time:** O(N^2), where N is the initial length of the string. The process involves N-2 operations. In operation `k` (0-indexed), we iterate through a string of length `N-k` to produce a new string of length `N-k-1`. The total number of elementary operations is proportional to the sum `(N-1) + (N-2) + ... + 2`, which is `O(N^2)`. · **Space:** O(N), where N is the initial length of the string. In each step of the simulation, a new `StringBuilder` and then a new `String` are created. The maximum length of this temporary storage is N-1.
**Pros:** It is straightforward to understand and implement as it directly translates the problem's description into code.; It works well for the given constraints.
**Cons:** The repeated creation of `StringBuilder` and `String` objects in each iteration introduces overhead, making it less performant than an array-based approach.; The time complexity is quadratic, which could be slow if the constraints on the string length were much larger.
### Explanation
The core of this method is a loop that executes as long as the string has more than two digits. In each iteration, we build a new string. We iterate through the current string, taking pairs of adjacent digits, summing them up, taking the result modulo 10, and appending the new digit to a temporary `StringBuilder`. Once we've processed all adjacent pairs, the `StringBuilder` contains the string for the next iteration. We replace our current string with this new one and repeat the process. The simulation stops when the string length becomes two, at which point we perform the final comparison.

```java
class Solution {
    public boolean areDigitsEqual(String s) {
        while (s.length() > 2) {
            StringBuilder next_s = new StringBuilder();
            for (int i = 0; i < s.length() - 1; i++) {
                int digit1 = s.charAt(i) - '0';
                int digit2 = s.charAt(i + 1) - '0';
                int sum = (digit1 + digit2) % 10;
                next_s.append(sum);
            }
            s = next_s.toString();
        }
        return s.charAt(0) == s.charAt(1);
    }
}
```
### Algorithm
- Start with the input string `s`.
- Use a `while` loop that continues as long as the length of the string is greater than 2.
- Inside the loop, create a new `StringBuilder` to store the result of the current operation.
- Iterate through the current string `s` from the first character up to the second-to-last character (index `i` from `0` to `s.length() - 2`).
- For each index `i`, get the integer values of the digits at `s.charAt(i)` and `s.charAt(i+1)`. 
- Calculate their sum modulo 10.
- Append this new digit to the `StringBuilder`.
- After the inner loop finishes, update `s` to the string representation of the `StringBuilder`.
- Once the `while` loop terminates (when `s.length() == 2`), compare the two characters of `s`.
- Return `true` if `s.charAt(0)` is equal to `s.charAt(1)`, and `false` otherwise.

## In-place Simulation with an Array
This approach is an optimization of the direct simulation. Instead of creating new string objects in each step, we convert the input string into an integer array at the beginning. Then, we perform all subsequent operations on this array, updating it in-place. This avoids the overhead associated with string object creation and garbage collection, leading to better practical performance.
**Time:** O(N^2). The number of nested loop iterations is identical to the first approach, leading to the same quadratic time complexity. The improvement is in the constant factor, not the asymptotic behavior. · **Space:** O(N), where N is the string length. We use an auxiliary integer array of size N to store the digits.
**Pros:** More efficient in practice than the string-based simulation by avoiding the overhead of creating new objects in each step.; Maintains the intuitive nature of the simulation.
**Cons:** While better than string manipulation, it still has a quadratic time complexity, which is not asymptotically optimal.
### Explanation
We begin by parsing the string of digits into an integer array. We then simulate the process by repeatedly iterating over this array. A variable `currentLen` keeps track of the logical size of our digit sequence. In each main step, we update the first `currentLen - 1` elements of the array: `digits[i]` becomes the sum of the old `digits[i]` and `digits[i+1]` modulo 10. After this inner loop, we decrease `currentLen` by one, effectively shortening our sequence. This continues until `currentLen` is 2. The final check is a simple comparison between `digits[0]` and `digits[1]`.

```java
class Solution {
    public boolean areDigitsEqual(String s) {
        int n = s.length();
        int[] digits = new int[n];
        for (int i = 0; i < n; i++) {
            digits[i] = s.charAt(i) - '0';
        }

        int currentLen = n;
        while (currentLen > 2) {
            for (int i = 0; i < currentLen - 1; i++) {
                digits[i] = (digits[i] + digits[i+1]) % 10;
            }
            currentLen--;
        }

        return digits[0] == digits[1];
    }
}
```
### Algorithm
- First, convert the input string `s` into an integer array, `digits`.
- Maintain a variable, `currentLen`, to track the effective length of the array, initialized to `s.length()`.
- Loop as long as `currentLen > 2`.
- In each iteration of the outer loop, run an inner loop from `i = 0` to `currentLen - 2`.
- Inside the inner loop, update `digits[i]` with the value `(digits[i] + digits[i+1]) % 10`. This overwrites the previous values in-place.
- After the inner loop completes, decrement `currentLen` by 1.
- When the loop terminates, the final two digits are at `digits[0]` and `digits[1]`. Return `true` if they are equal, `false` otherwise.

## Mathematical Approach via Binomial Coefficients
This advanced approach leverages mathematical insights to bypass the simulation entirely. By analyzing the transformation process, we can see that the final digits are a linear combination of the initial digits. The coefficients of this combination are binomial coefficients. This allows us to formulate a direct mathematical expression for the final two digits and check for their equality without performing the intermediate steps.
**Time:** O(N log N). The main loop runs `N-2` times. Inside the loop, computing the binomial coefficient `C(N-2, j) % 10` using Lucas's Theorem takes `O(log_5 N)` time. Thus, the total time complexity is dominated by this calculation within the loop. · **Space:** O(N) to store the initial digits in an array. The space for helper tables is constant.
**Pros:** Asymptotically the most efficient approach with a time complexity of O(N log N).; Avoids the O(N^2) simulation, making it significantly faster for larger N.
**Cons:** Significantly more complex to understand and implement correctly.; Requires knowledge of number theory concepts like binomial coefficients, Lucas's Theorem, and the Chinese Remainder Theorem.
### Explanation
After `m = N-2` operations, the final two digits, `final_0` and `final_1`, can be expressed in terms of the initial digits `d_0, d_1, ..., d_{N-1}` and binomial coefficients `C(m, j)`:
`final_0 = (Σ_{j=0 to m} d_j * C(m, j)) % 10`
`final_1 = (Σ_{j=0 to m} d_{j+1} * C(m, j)) % 10`

We need to check if `final_0 == final_1`, which simplifies to checking if `(final_0 - final_1) % 10 == 0`. This is equivalent to checking if `(Σ_{j=0 to m} (d_j - d_{j+1}) * C(m, j)) % 10 == 0`.

The main challenge is computing `C(m, j) % 10`. We do this using the Chinese Remainder Theorem by finding the coefficient modulo 2 and 5. Lucas's Theorem gives us a fast way to do this. Once we have a function to compute `C(m, j) % 10`, we can iterate from `j=0` to `m`, calculate each term in the sum, and check if the final sum is divisible by 10.

```java
class Solution {
    private static final int[][] C_MOD_5 = {
        {1, 0, 0, 0, 0}, {1, 1, 0, 0, 0}, {1, 2, 1, 0, 0},
        {1, 3, 3, 1, 0}, {1, 4, 1, 4, 1}
    };

    private int combinationsModP(int n, int k, int p, int[][] c_table) {
        if (k < 0 || k > n) return 0;
        int res = 1;
        while (n > 0) {
            int ni = n % p;
            int ki = k % p;
            if (ki > ni) return 0;
            res = (res * c_table[ni][ki]) % p;
            n /= p;
            k /= p;
        }
        return res;
    }

    private int combinationsMod2(int n, int k) {
        if (k < 0 || k > n) return 0;
        return ((k & n) == k) ? 1 : 0;
    }

    private int combinationsMod10(int n, int k) {
        int c2 = combinationsMod2(n, k);
        int c5 = combinationsModP(n, k, 5, C_MOD_5);
        int a = (c2 - c5 + 2) % 2;
        return 5 * a + c5;
    }

    public boolean areDigitsEqual(String s) {
        int n = s.length();
        int m = n - 2;

        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = s.charAt(i) - '0';
        }

        int totalSum = 0;
        for (int j = 0; j <= m; j++) {
            int coeff = combinationsMod10(m, j);
            int diff = d[j] - d[j + 1];
            totalSum += diff * coeff;
        }
        
        return totalSum % 10 == 0;
    }
}
```
### Algorithm
- Let `N` be the length of the string `s`, and `m = N-2`. Convert `s` to an integer array `d`.
- The problem is equivalent to checking if the sum `S = Σ_{j=0 to m} (d_j - d_{j+1}) * C(m, j)` is divisible by 10.
- The main task is to compute the binomial coefficients `C(m, j) % 10` for `j` from 0 to `m`.
- Since 10 is a composite number (2 * 5), we use the Chinese Remainder Theorem (CRT). We compute `C(m, j) % 2` and `C(m, j) % 5` separately and then combine them.
- Lucas's Theorem provides an efficient way to compute these values:
  - `C(m, j) % 2` is 1 if and only if `(j & m) == j` (in terms of bitwise operations).
  - `C(m, j) % 5` is found by expressing `m` and `j` in base 5, say `m = m_k...m_0` and `j = j_k...j_0`, and then computing `(Π C(m_i, j_i)) % 5`.
- The overall algorithm is:
  1. Initialize a total sum to 0.
  2. Loop `j` from 0 to `m`.
  3. In each iteration, compute `coeff = C(m, j) % 10` using the method described above.
  4. Calculate `term = (d[j] - d[j+1]) * coeff`.
  5. Add `term` to the total sum.
  6. After the loop, check if `total_sum % 10 == 0`.

# Solutions
### Java

```java
class Solution {
public
  boolean hasSameDigits(String s) {
    char[] t = s.toCharArray();
    int n = t.length;
    for (int k = n - 1; k > 1; --k) {
      for (int i = 0; i < k; ++i) {
        t[i] = (char)((t[i] - '0' + t[i + 1] - '0') % 10 + '0');
      }
    }
    return t[0] == t[1];
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool hasSameDigits(string s) {
    int n = s.size();
    string t = s;
    for (int k = n - 1; k > 1; --k) {
      for (int i = 0; i < k; ++i) {
        t[i] = (t[i] - '0' + t[i + 1] - '0') % 10 + '0';
      }
    }
    return t[0] == t[1];
  }
};

```

### Python

```python
class Solution:
    def hasSameDigits(self, s: str) -> bool: t = list(map(int, s)) n = len(t) for k in range(n - 1, 1, - 1): for i in range(k): t[i] = (t[i] + t[i + 1]) % 10 return t[0] == t[1]

```