Check If Digits Are Equal in String After Operations I
EasyPrompt
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
swith 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 = 2sbecomes"292"
- Second operation:
(s[0] + s[1]) % 10 = (2 + 9) % 10 = 1(s[1] + s[2]) % 10 = (9 + 2) % 10 = 1sbecomes"11"
- Since the digits in
"11"are the same, the output istrue.
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 isfalse.
Constraints:
3 <= s.length <= 100sconsists of only digits.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Start with the input string
s. - Use a
whileloop that continues as long as the length of the string is greater than 2. - Inside the loop, create a new
StringBuilderto store the result of the current operation. - Iterate through the current string
sfrom the first character up to the second-to-last character (indexifrom0tos.length() - 2). - For each index
i, get the integer values of the digits ats.charAt(i)ands.charAt(i+1). - Calculate their sum modulo 10.
- Append this new digit to the
StringBuilder. - After the inner loop finishes, update
sto the string representation of theStringBuilder. - Once the
whileloop terminates (whens.length() == 2), compare the two characters ofs. - Return
trueifs.charAt(0)is equal tos.charAt(1), andfalseotherwise.
Walkthrough
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.
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); }}Complexity
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.
Trade-offs
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
StringBuilderandStringobjects 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.
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.
Algorithm
- First, convert the input string
sinto an integer array,digits. - Maintain a variable,
currentLen, to track the effective length of the array, initialized tos.length(). - Loop as long as
currentLen > 2. - In each iteration of the outer loop, run an inner loop from
i = 0tocurrentLen - 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
currentLenby 1. - When the loop terminates, the final two digits are at
digits[0]anddigits[1]. Returntrueif they are equal,falseotherwise.
Walkthrough
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].
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]; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Let
Nbe the length of the strings, andm = N-2. Convertsto an integer arrayd. - 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) % 10forjfrom 0 tom. - Since 10 is a composite number (2 * 5), we use the Chinese Remainder Theorem (CRT). We compute
C(m, j) % 2andC(m, j) % 5separately and then combine them. - Lucas's Theorem provides an efficient way to compute these values:
C(m, j) % 2is 1 if and only if(j & m) == j(in terms of bitwise operations).C(m, j) % 5is found by expressingmandjin base 5, saym = m_k...m_0andj = j_k...j_0, and then computing(Π C(m_i, j_i)) % 5.
- The overall algorithm is:
- Initialize a total sum to 0.
- Loop
jfrom 0 tom. - In each iteration, compute
coeff = C(m, j) % 10using the method described above. - Calculate
term = (d[j] - d[j+1]) * coeff. - Add
termto the total sum. - After the loop, check if
total_sum % 10 == 0.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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]; }}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]; }};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]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.