Sum of Digits of String After Convert

Easy

#1774Time: O(N + k * L), where N is the length of the input string `s` and L is the length of the number string. The initial conversion is O(N). The first transformation operates on a string of length up to 2N. Subsequent transformations are on much smaller numbers. The complexity is dominated by the initial conversion and the first transformation, making it effectively O(N), but with higher constant factors due to string operations.Space: O(N), as a `StringBuilder` and string of length up to 2N are created to store the number after the initial conversion.

Data structures

String

Prompt

You are given a string s consisting of lowercase English letters, and an integer k. Your task is to convert the string into an integer by a special process, and then transform it by summing its digits repeatedly k times. More specifically, perform the following steps:

Convert s into an integer by replacing each letter with its position in the alphabet (i.e. replace 'a' with 1, 'b' with 2, ..., 'z' with 26).
Transform the integer by replacing it with the sum of its digits.
Repeat the transform operation (step 2) k times in total.

For example, if s = "zbax" and k = 2, then the resulting integer would be 8 by the following operations:

Convert: "zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
Transform #1: 262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
Transform #2: 17 ➝ 1 + 7 ➝ 8

Return the resulting integer after performing the operations described above.

Example 1:

Input: s = "iiii", k = 1

Output: 36

Explanation:

The operations are as follows:
- Convert: "iiii" ➝ "(9)(9)(9)(9)" ➝ "9999" ➝ 9999
- Transform #1: 9999 ➝ 9 + 9 + 9 + 9 ➝ 36
Thus the resulting integer is 36.

Example 2:

Input: s = "leetcode", k = 2

Output: 6

Explanation:

The operations are as follows:
- Convert: "leetcode" ➝ "(12)(5)(5)(20)(3)(15)(4)(5)" ➝ "12552031545" ➝ 12552031545
- Transform #1: 12552031545 ➝ 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ➝ 33
- Transform #2: 33 ➝ 3 + 3 ➝ 6
Thus the resulting integer is 6.

Example 3:

Input: s = "zbax", k = 2

Output: 8

Constraints:

1 <= s.length <= 100
1 <= k <= 10
s consists of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem statement. It first converts the input string s into a new, potentially very long, string of digits. Then, it iteratively calculates the sum of digits of this string k times, updating the string at each step.

Algorithm

Create a StringBuilder to store the numeric representation of the string s.
Iterate through s, converting each character c to c - 'a' + 1 and appending it to the StringBuilder.
Convert the StringBuilder to a string numStr.
Loop k times:
- Calculate the sum of digits of numStr.
- Update numStr with the string representation of the sum.
Return the final sum as an integer.

Walkthrough

The core idea is to use string manipulation to handle the large number generated in the 'convert' step.

The algorithm proceeds as follows:

Initialize a StringBuilder to construct the number string.
Iterate through each character of the input string s. For each character c, find its corresponding alphabetical position (e.g., 'a' -> 1, 'b' -> 2). Append this numeric value to the StringBuilder.
After processing all characters, you will have a string, let's call it numStr, representing the converted number.
Start a loop to perform the transformation k times.
In each iteration of the loop, calculate the sum of the digits of the current numStr.
To do this, initialize a sum variable to 0. Iterate through the characters of numStr, convert each character to its integer value, and add it to sum.
After summing the digits, update numStr to be the string representation of the calculated sum.
After k iterations, the final numStr holds the string representation of the answer. Convert it to an integer and return.

Here is the Java implementation for this approach:

1class Solution {2    public int getLucky(String s, int k) {3        StringBuilder sb = new StringBuilder();4        for (char c : s.toCharArray()) {5            sb.append(c - 'a' + 1);6        }7        String numStr = sb.toString();8        long sum = 0;9 10        // Perform the transformation k times11        for (int i = 0; i < k; i++) {12            sum = 0;13            for (char digitChar : numStr.toCharArray()) {14                sum += digitChar - '0';15            }16            numStr = String.valueOf(sum);17        }18        return (int) sum;19    }20}

Complexity

Time

O(N + k * L), where N is the length of the input string `s` and L is the length of the number string. The initial conversion is O(N). The first transformation operates on a string of length up to 2N. Subsequent transformations are on much smaller numbers. The complexity is dominated by the initial conversion and the first transformation, making it effectively O(N), but with higher constant factors due to string operations.

Space

O(N), as a `StringBuilder` and string of length up to 2N are created to store the number after the initial conversion.

Trade-offs

Pros

- The logic is straightforward and directly follows the problem description, making it easy to understand and implement.

Cons

- This approach is inefficient because it involves creating a potentially large intermediate string.
- Repeated conversions between strings and numbers inside the loop add performance overhead.

This approach avoids the creation of a large intermediate string by leveraging a mathematical property: the sum of digits of a concatenated number is equal to the sum of the sums of digits of its constituent parts. For example, the sum of digits of 1234 is the same as the sum of digits of 12 plus the sum of digits of 34. This allows us to compute the result of the first transformation directly without building the string.

Algorithm

Initialize an integer sum = 0.
Iterate through the input string s. For each character c:
- Calculate its value val = c - 'a' + 1.
- Add the sum of digits of val to the total sum.
This completes the first transformation.
Loop k-1 more times:
- Replace sum with the sum of its own digits.
Return the final sum.

Walkthrough

Instead of building a large string like '12552031545' and then summing its digits, we can calculate the sum of digits for each character's value as we iterate through the input string.

The algorithm is as follows:

Initialize an integer sum to 0. This variable will hold the result of the first transformation.
Iterate through each character c of the input string s.
For each character, calculate its value val = c - 'a' + 1.
Calculate the sum of the digits of val and add it to the total sum. Since val is between 1 and 26, this is a simple operation (e.g., val / 10 + val % 10).
After the loop, sum contains the result of one transformation.
Now, perform the remaining k-1 transformations. Loop from i = 1 to k-1.
In each iteration, calculate the sum of digits of the current sum and update sum with this new value.
After the loops complete, sum holds the final result.

Here is the Java implementation for this optimized approach:

1class Solution {2    public int getLucky(String s, int k) {3        int sum = 0;4        // Calculate the sum for the first transformation directly5        for (char c : s.toCharArray()) {6            int val = c - 'a' + 1;7            sum += (val / 10) + (val % 10);8        }9 10        // Perform the remaining k-1 transformations11        for (int i = 1; i < k; i++) {12            int nextSum = 0;13            while (sum > 0) {14                nextSum += sum % 10;15                sum /= 10;16            }17            sum = nextSum;18        }19        return sum;20    }21}

Complexity

Time

O(N), where N is the length of the input string `s`. The initial pass over the string takes O(N) time. The subsequent `k-1` transformations operate on a number that shrinks very quickly, so this part takes negligible time compared to the initial pass.

Space

O(1), as we only use a few integer variables for the calculation, requiring constant extra space regardless of the input size.

Trade-offs

Pros

- Highly efficient in both time and space.
- Avoids costly string creation and manipulation, leading to better performance.

Cons

- The logic is slightly less direct than the brute-force approach, as it relies on observing a property of digit sums.

Solutions

Solution

1class Solution {2public3  int getLucky(String s, int k) {4    StringBuilder sb = new StringBuilder();5    for (char c : s.toCharArray()) {6      sb.append(c - 'a' + 1);7    }8    s = sb.toString();9    while (k-- > 0) {10      int t = 0;11      for (char c : s.toCharArray()) {12        t += c - '0';13      }14      s = String.valueOf(t);15    }16    return Integer.parseInt(s);17  }18}

1class Solution {2public:3  int getLucky(string s, int k) {4    string t;5    for (char c : s)6      t += to_string(c - 'a' + 1);7    s = t;8    while (k--) {9      int t = 0;10      for (char c : s)11        t += c - '0';12      s = to_string(t);13    }14    return stoi(s);15  }16};

1class Solution:2    def getLucky(self, s: str, k: int) -> int: s = '' . join(str(ord(c) - ord('a') + 1) for c in s) for _ in range(k): t = sum(int(c) for c in s) s = str(t) return int(s)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem