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:
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.s with a string representing the sum of all its digits. For example, "346" is replaced with "13" because 3 + 4 + 6 = 13.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 <= 1002 <= k <= 100s consists of digits only.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.
C++
Java
Python
C#
JavaScript
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).
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.
C++
Java
Python
C#
JavaScript
The time complexity is O(n * m), while the call stack space usage also leads to O(n) space complexity overall.
| Approach | Complexity |
|---|---|
| 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. |
Calculate Digit Sum of a String | Leetcode 2243 | Strings | Contest 289 🔥🔥 • Coding Decoded • 2,260 views views
Watch 9 more video solutions →Practice Calculate Digit Sum of a String with our built-in code editor and test cases.
Practice on FleetCode