2243. Calculate Digit Sum of a String - Solution

Q: 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.

Q: 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.

Q: 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).

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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:

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.
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.
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.

Python

def digit_sum_string(s, k):
    while len(s) > k:
        new_s = ''
        for i in range(0, len(s), k):
            group = s[i:i + k]
            digit_sum = sum(int(char) for char in group)
            new_s += str(digit_sum)
        s = new_s
    return s

# Example usage:
s = "11111222223"
k = 3
print(digit_sum_string(s, k))  # Output: "135"

Java

public class DigitSum {
    public static String digitSumString(String s, int k) {
        while (s.length() > k) {
            StringBuilder newString = 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';
                }
                newString.append(sum);
            }
            s = newString.toString();
        }
        return s;
    }

    public static void main(String[] args) {
        String s = "11111222223";
        int k = 3;
        System.out.println(digitSumString(s, k)); // Output: "135"
    }
}

C++

#include <iostream>
#include <string>

std::string digitSumString(const std::string &s, int k) {
    std::string current = s;
    while (current.size() > k) {
        std::string new_s = "";
        for (size_t i = 0; i < current.size(); i += k) {
            int sum = 0;
            for (size_t j = i; j < i + k && j < current.size(); ++j) {
                sum += current[j] - '0';
            }
            new_s += std::to_string(sum);
        }
        current = new_s;
    }
    return current;
}

int main() {
    std::string s = "11111222223";
    int k = 3;
    std::cout << digitSumString(s, k) << std::endl; // Output: "135"
    return 0;
}

JavaScript

function digitSumString(s, k) {
    while (s.length > k) {
        let new_s = '';
        for (let i = 0; i < s.length; i += k) {
            let sum = 0;
            for (let j = i; j < i + k && j < s.length; j++) {
                sum += parseInt(s[j]);
            }
            new_s += sum.toString();
        }
        s = new_s;
    }
    return s;
}

// Example usage:
const s = "11111222223";
const k = 3;
console.log(digitSumString(s, k)); // Output: "135"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* digitSumString(char* s, int k) {
    int n = strlen(s);
    while (n > k) {
        int newLen = (n + k - 1) / k; // Calculate number of new groups
        char* new_s = (char*)malloc(newLen * sizeof(char) + 1);
        int index = 0;
        for (int i = 0; i < n; i += k) {
            int sum = 0;
            for (int j = i; j < i + k && j < n; ++j) {
                sum += s[j] - '0';
            }
            sprintf(new_s + index, "%d", sum);
            index += strlen(new_s + index);
        }
        new_s[index] = '\0';
        s = new_s;
        n = strlen(s);
    }
    return s;
}

int main() {
    char s[] = "11111222223";
    int k = 3;
    printf("%s\n", digitSumString(s, k)); // Output: "135"
    return 0;
}

using System;

public class Solution {
    public static string DigitSumString(string s, int k) {
        while (s.Length > k) {
            string new_s = "";
            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[j] - '0';
                }
                new_s += sum.ToString();
            }
            s = new_s;
        }
        return s;
    }

    public static void Main() {
        string s = "11111222223";
        int k = 3;
        Console.WriteLine(DigitSumString(s, k)); // Output: "135"
    }
}

The Python solution effectively splits the string into segments, computes the digit sum of each segment, assembles a new string from these sums, and repeats the process until the new string length is at most k.

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.

Python

def digit_sum_string_recursive(s, k):
    if len(s) <= k:
        return s
    new_s = ''
    for i in range(0, len(s), k):
        group = s[i:i + k]
        digit_sum = sum(int(char) for char in group)
        new_s += str(digit_sum)
    return digit_sum_string_recursive(new_s, k)

# Example usage:
s = "11111222223"
k = 3
print(digit_sum_string_recursive(s, k))  # Output: "135"

Java

public class DigitSumRecursive {
    public static String digitSumString(String s, int k) {
        if (s.length() <= k) return s;
        StringBuilder newString = 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';
            }
            newString.append(sum);
        }
        return digitSumString(newString.toString(), k);
    }

    public static void main(String[] args) {
        String s = "11111222223";
        int k = 3;
        System.out.println(digitSumString(s, k)); // Output: "135"
    }
}

C++

#include <iostream>
#include <string>

std::string digitSumStringRecursive(const std::string &s, int k) {
    if (s.size() <= k) return s;
    std::string new_s = "";
    for (size_t i = 0; i < s.size(); i += k) {
        int sum = 0;
        for (size_t j = i; j < i + k && j < s.size(); ++j) {
            sum += s[j] - '0';
        }
        new_s += std::to_string(sum);
    }
    return digitSumStringRecursive(new_s, k);
}

int main() {
    std::string s = "11111222223";
    int k = 3;
    std::cout << digitSumStringRecursive(s, k) << std::endl; // Output: "135"
    return 0;
}

JavaScript

function digitSumStringRecursive(s, k) {
    if (s.length <= k) return s;
    let new_s = '';
    for (let i = 0; i < s.length; i += k) {
        let sum = 0;
        for (let j = i; j < i + k && j < s.length; j++) {
            sum += parseInt(s[j]);
        }
        new_s += sum.toString();
    }
    return digitSumStringRecursive(new_s, k);
}

// Example usage:
const s = "11111222223";
const k = 3;
console.log(digitSumStringRecursive(s, k)); // Output: "135"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* digitSumStringRecursive(char* s, int k) {
    int n = strlen(s);
    if (n <= k) return s;
    int newLen = (n + k - 1) / k; // Calculate number of new groups
    char* new_s = (char*)malloc(newLen * sizeof(char) + 1);
    int index = 0;
    for (int i = 0; i < n; i += k) {
        int sum = 0;
        for (int j = i; j < i + k && j < n; ++j) {
            sum += s[j] - '0';
        }
        sprintf(new_s + index, "%d", sum);
        index += strlen(new_s + index);
    }
    new_s[index] = '\0';
    return digitSumStringRecursive(new_s, k);
}

int main() {
    char s[] = "11111222223";
    int k = 3;
    printf("%s\n", digitSumStringRecursive(s, k)); // Output: "135"
    return 0;
}

using System;

public class SolutionRecursive {
    public static string DigitSumString(string s, int k) {
        if (s.Length <= k) return s;
        string new_s = "";
        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[j] - '0';
            }
            new_s += sum.ToString();
        }
        return DigitSumString(new_s, k);
    }

    public static void Main() {
        string s = "11111222223";
        int k = 3;
        Console.WriteLine(DigitSumString(s, k)); // Output: "135"
    }
}

By applying recursion, the Python code repeats the string transformation process after summing and reformulating until an adequate length is achieved, mimicking iterative logic recursively.

Complexity

Given the recursive nature, it has a runtime complexity of O(n * m) and space complexity from stack depth being O(n).

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.

TypeScript

function digitSum(s: string, k: number): string {
    while (s.length > k) {
        const t: number[] = [];
        for (let i = 0; i < s.length; i += k) {
            const x = s
                .slice(i, i + k)
                .split('')
                .reduce((a, b) => a + +b, 0);
            t.push(x);
        }
        s = t.join('');
    }
    return s;
}

func digitSum(s string, k int) string {
	for len(s) > k {
		t := &strings.Builder{}
		n := len(s)
		for i := 0; i < n; i += k {
			x := 0
			for j := i; j < i+k && j < n; j++ {
				x += int(s[j] - '0')
			}
			t.WriteString(strconv.Itoa(x))
		}
		s = t.String()
	}
	return s
}

Rust

impl Solution {
    pub fn digit_sum(s: String, k: i32) -> String {
        let mut s = s;
        let k = k as usize;
        while s.len() > k {
            let mut t = Vec::new();
            for chunk in s.as_bytes().chunks(k) {
                let sum: i32 = chunk.iter().map(|&c| (c - b'0') as i32).sum();
                t.push(sum.to_string());
            }
            s = t.join("");
        }
        s
    }
}

Try this approach in the editor

Complexity comparison

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	Given the recursive nature, it has a runtime complexity of O(n * m) and space complexity from stack depth being O(n).
Simulation	–

Complexity analysis

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

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.

Calculate Digit Sum of a String solution and explanation

The problem

Approach overview

Approach 1: Iterative Approach

Approach 2: Recursive Approach

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Calculate Digit Sum of a String solution and explanation

The problem

Approach overview

Approach 1: Iterative Approach

Approach 2: Recursive Approach

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems