2243. Calculate Digit Sum of a String
- String
- Simulation
TIME
O(n), the length shrinks geometrically (every other round when k = 2)
SPACE
O(n)
Intuition
The statement spells out the procedure, so simulate it. The only real question is whether it finishes quickly. It does:
- For
k >= 3, a full group ofkdigits sums to at most9k, which has fewer thankdigits (27 has 2, 900 has 3). Every round shrinks the string by a constant factor. - For
k = 2, a pair sums to at most 18, so a round can keep the length unchanged, but only if every pair sums to 10 or more. Then the new string is made of blocks"1d"withd <= 8, the next round's pairs line up with those blocks, and each sums to1 + d <= 9, a single digit. So the length at least halves every two rounds.
Either way the lengths form a geometric series, and the total work is O(n).
Approach
- While
len(s) > k:- Walk
sin steps ofk, sum the digits of each chunk (the last chunk may be shorter). - Append each sum as a decimal string and replace
swith the result.
- Walk
- Return
s.
Complexity
- Time: O(n). Round lengths shrink geometrically, so their total is O(n). Measured worst at
n = 100: 398 characters processed across 12 rounds, withk = 2. - Space: O(n) for the next round's string
Edge Cases
len(s) <= kfrom the start: no rounds, returnsunchanged- Zeros (example 2): a group of zeros becomes
"0", not an empty string, so the length still counts it - The last group can be shorter than
k, even a single digit k = 2with large digits ("999"): the first round gives"189", the same length, then"99"- A group sum can have up to 3 digits (
k = 100, all nines: 900), so append the sum as a string, not a single character
Code
class Solution:
def digitSum(self, s: str, k: int) -> str:
"""
2243. Calculate Digit Sum of a String
Time: O(n), the length shrinks geometrically (every other round when k = 2)
Space: O(n)
"""
while len(s) > k:
s = "".join(
str(sum(int(c) for c in s[i:i + k])) for i in range(0, len(s), k)
)
return s/**
* 2243. Calculate Digit Sum of a String
* Time: O(n), the length shrinks geometrically (every other round when k = 2)
* Space: O(n)
*/
class Solution {
public String digitSum(String s, int k) {
while (s.length() > k) {
StringBuilder next = new StringBuilder();
for (int i = 0; i < s.length(); i += k) {
int sum = 0;
for (int j = i; j < Math.min(i + k, s.length()); j++) {
sum += s.charAt(j) - '0';
}
next.append(sum);
}
s = next.toString();
}
return s;
}
}