Calculate Digit Sum of a String — Problem & Solution
Calculate Digit Sum of a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Calculate Digit Sum of a String is an easy coding problem on strings and simulation, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Strings, Simulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string of digits s and an integer k. While s is longer than k, perform a round:
- Cut
sinto consecutive groups ofkcharacters — the firstkcharacters, the nextk, and so on; the last group may be shorter. - Replace every group by the decimal representation of the sum of its digits (so
"346"becomes"13"). - Concatenate the results, in order, to form the new
s.
Return s once its length is at most k.
Example 1
Input: s = "20261002", k = 3
Output: 472
Explanation: Groups `202`, `610`, `02` sum to 4, 7 and 2.
Example 2
Input: s = "9999", k = 2
Output: 99
Explanation: `9999` → `1818` → `99`.
Example 3
Input: s = "12", k = 5
Output: 12
Explanation: Already short enough — no rounds.
Constraints
1 <= s.length <= 1002 <= k <= 100s consists of digits only
Hints for Calculate Digit Sum of a String
Hint 1
Simulate the rounds exactly as described.
Hint 2
In each round step through
sin strides ofkand sum the digits of each slice.Hint 3
Append each sum as text (it may have more than one digit) and loop until the length is at most
k.
How to solve Calculate Digit Sum of a String
The process is fully specified and short-lived, so simulate it: each round turns every group of k digits into the text of its digit sum.
Approach
- While
len(s) > k: - Build
nextby walkingi = 0, k, 2k, …, summing the digits ofs[i .. i+k)(clipped at the end) and appending the sum's decimal text. - Set
s = next. - Return
s.
Why it works
The loop applies the round literally, so its result is the defined one. It always stops: a full group whose sum is a single digit makes the string shorter, and a group whose sum has two or more digits makes the total digit sum strictly smaller (a number's digit sum is below the number once it reaches 10), so the string cannot stay long forever.
Complexity
- Time —
O(n) per round, and the length drops quickly - Space —
O(n)
Pitfalls
- A group sum can have several digits (
"99"→"18") — append all of them. - The last group may be shorter than
k; do not read past the end. - Stop when the length is
<= k, not< k.
Reference solution
Python
def digitSum(s: str, k: int) -> str:
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 sJava
public static 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 < i + k && j < s.length(); j++) sum += s.charAt(j) - '0';
next.append(sum);
}
s = next.toString();
}
return s;
}C++
string digitSum(string s, int k) {
while ((int)s.size() > k) {
string next;
for (int i = 0; i < (int)s.size(); i += k) {
int sum = 0;
for (int j = i; j < i + k && j < (int)s.size(); j++) sum += s[j] - '0';
next += to_string(sum);
}
s = next;
}
return s;
}JavaScript
var digitSum = function(s, k) {
while (s.length > k) {
var next = "";
for (var i = 0; i < s.length; i += k) {
var sum = 0;
for (var j = i; j < i + k && j < s.length; j++) sum += s.charCodeAt(j) - 48;
next += String(sum);
}
s = next;
}
return s;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings