Skip to main content
Talentd

Calculate Digit Sum of a String - Solution & Explanation

EasyStringSimulation18 min readAsked at: Uber
Practice this problem

Problem Statement

You are given a string s consisting of digits and an integer k.

A round can be completed if the length of s is greater than k. In one round, do the following:

  1. Divide s into consecutive groups of size k such that the first k characters are in the first group, the next k characters are in the second group, and so on. Note that the size of the last group can be smaller than k.
  2. Replace each group of s with a string representing the sum of all its digits. For example, "346" is replaced with "13" because 3 + 4 + 6 = 13.
  3. Merge consecutive groups together to form a new string. If the length of the string is greater than k, repeat from step 1.

Return s after all rounds have been completed.

 

Example 1:

Input: s = "11111222223", k = 3
Output: "135"
Explanation: 
- For the first round, we divide s into groups of size 3: "111", "112", "222", and "23".
  ​​​​​Then we calculate the digit sum of each group: 1 + 1 + 1 = 3, 1 + 1 + 2 = 4, 2 + 2 + 2 = 6, and 2 + 3 = 5. 
  So, s becomes "3" + "4" + "6" + "5" = "3465" after the first round.
- For the second round, we divide s into "346" and "5".
  Then we calculate the digit sum of each group: 3 + 4 + 6 = 13, 5 = 5. 
  So, s becomes "13" + "5" = "135" after second round. 
Now, s.length <= k, so we return "135" as the answer.

Example 2:

Input: s = "00000000", k = 3
Output: "000"
Explanation: 
We divide s into "000", "000", and "00".
Then we calculate the digit sum of each group: 0 + 0 + 0 = 0, 0 + 0 + 0 = 0, and 0 + 0 = 0. 
s becomes "0" + "0" + "0" = "000", whose length is equal to k, so we return "000".

 

Constraints:

  • 1 <= s.length <= 100
  • 2 <= k <= 100
  • s consists of digits only.

Approach Overview

Problem Overview: You are given a numeric string s and an integer k. Repeatedly split the string into groups of size k, compute the digit sum of each group, and concatenate those sums to form a new string. Continue the process until the string length becomes less than or equal to k.

Approach 1: Iterative Simulation (O(n) time, O(n) space)

This approach directly simulates the process described in the problem. While the string length is greater than k, iterate through the string in chunks of size k. For each chunk, convert characters to digits, compute the sum, and append the result to a new string builder. After processing all groups, replace the original string with the newly constructed string and repeat the process. Each digit participates in a small constant number of summations across iterations, keeping the total time complexity O(n) and space O(n). This is the most practical solution and relies on simple string manipulation and simulation.

Approach 2: Recursive Simulation (O(n) time, O(n) space)

The same grouping logic can be expressed recursively. Define a function that takes the current string. If its length is less than or equal to k, return it as the base case. Otherwise, iterate through the string in steps of k, compute the digit sum for each segment, and build the next string. Then recursively call the function with this newly generated string. Each recursive call reduces the string length, so the recursion depth remains small. Time complexity stays O(n) since each digit is processed a limited number of times, while auxiliary space is O(n) due to the new strings created and recursion stack. This version highlights the repeated transformation pattern and demonstrates a clean use of recursion.

Recommended for interviews: The iterative simulation approach is what interviewers typically expect. It directly follows the problem statement, avoids recursion overhead, and clearly demonstrates control over string iteration and chunk processing. Implementing the recursive variant can show deeper understanding of problem structure, but the iterative solution is simpler, easier to reason about, and usually preferred in production code.

Approach 1: Iterative Approach

The iterative approach involves reducing the problem step by step. We use a loop to partition the string into groups, sum the digits in each group, and form a new string. This process is repeated until the length of the new string is less than or equal to k.

The C code uses dynamic memory allocation to handle repeated transformation of the string. During each iteration, the string is partitioned, digit sums are calculated for each group, and a new string is constructed from these sums. This continues until the resulting string's length is not greater than k.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n * m), where n is the length of the string and m is log base 10 of the sum of digits. The space complexity is O(n).

Try this approach in the editor →

Approach 2: Recursive Approach

The recursive approach uses a function to perform the digit summation operation once and calls itself as long as the resulting string has a length greater than k. This method translates the iterative mechanism into a recursion pattern.

In C, recursion is used to call the digitSumStringRecursive function repeatedly if the result's length is greater than k. This effectively captures the same repeated operation pattern as iterative methods, but through recursive calls.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity is O(n * m), while the call stack space usage also leads to O(n) space complexity overall.

Try this approach in the editor →

Approach 3: Simulation

According to the problem statement, we can simulate the operations described in the problem until the length of the string is less than or equal to k. Finally, return the string.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the string s.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach

The time complexity is O(n * m), where n is the length of the string and m is log base 10 of the sum of digits. The space complexity is O(n).

Recursive Approach

The time complexity is O(n * m), while the call stack space usage also leads to O(n) space complexity overall.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative SimulationO(n)O(n)Best general solution. Simple loop-based implementation and preferred for interviews.
Recursive SimulationO(n)O(n)Useful when expressing repeated transformations recursively or practicing recursion patterns.

Video Solution

Calculate Digit Sum of a String | Leetcode 2243 | Strings | Contest 289 🔥🔥 • Coding Decoded • 2,385 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Calculate Digit Sum of a String easy or hard?
Calculate Digit Sum of a String is classified as an Easy problem. The challenge focuses on correctly simulating the transformation process and managing string grouping without unnecessary complexity.
Calculate Digit Sum of a String Python/Java solution
In Python or Java, iterate over the string with a step of k, sum the digits in each substring, and append the sum to a result string or StringBuilder. Repeat until the string length becomes ≤ k. Both implementations run in O(n) time and O(n) space.
How to solve Calculate Digit Sum of a String in O(n)?
Process the string in chunks of size k and compute the digit sum for each chunk using a loop. Append each sum to a new string and repeat the grouping process until the resulting string length becomes less than or equal to k. Since each digit is handled a limited number of times, the total complexity remains O(n).
What is the best approach for Calculate Digit Sum of a String?
The iterative simulation approach is the most efficient and easiest to implement. Iterate through the string in groups of k, compute the digit sum of each group, and build a new string until its length becomes ≤ k. This method runs in O(n) time with O(n) space.
Is Calculate Digit Sum of a String asked at Google/Amazon/Meta?
Problems involving string simulation and digit manipulation appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, similar tasks test your ability to simulate transformations and manage string processing efficiently.
What data structure is used in Calculate Digit Sum of a String?
The problem mainly uses strings or string builders to construct intermediate results. No complex data structures are required. The solution relies on sequential traversal, digit conversion, and concatenation operations.
What is the time complexity of Calculate Digit Sum of a String?
The overall time complexity is O(n). Each iteration processes the current string by summing groups of digits, and the string size shrinks quickly after each transformation. Every character participates in only a small number of operations across all rounds.

Ready to solve this problem?

Practice Calculate Digit Sum of a String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Digits

Next

Find Triangular Sum of an Array