Problem of The Day: Sum of Digits of String After Convert

Problem Statement

Intuition

When I first encountered this problem, my immediate thought was to convert each character in the string into its corresponding numeric value based on its position in the alphabet. Then, by summing these digits multiple times as required, I could gradually reduce the number until the transformation process is complete.

Approach

I began by iterating through the string, converting each character into its numeric equivalent and then concatenating these numbers to form a large number string. The core of the solution is to repeatedly sum the digits of this number string k times, transforming the result in each iteration until the final value is obtained. This approach ensures that the transformations are performed exactly k times, reducing the number down step by step.

Complexity

• Time complexity: The time complexity is determined by the length of the string and the number of transformations k. The conversion of each character into a digit is \(O(n)\), and each transformation step also takes linear time, leading to an overall complexity of \(O(n \cdot k)\).
• Space complexity: The space complexity is primarily \(O(n)\), where n is the length of the string. This space is needed to store the intermediate digit string.

Code

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        digits = ""
        for c in s:
            digit = int(ord(c) - ord('a') + 1)
            digits += str(digit)

        res = 0
        while k > 0:
            res = 0
            for digit in digits:
                res += int(digit)
            digits = str(res)
            k -= 1
        return res

Editorial

Approach 1: String Concatenation to Summation

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        # Convert each character to its numerical value and build a string
        numeric_string = ""
        for ch in s:
            numeric_string += str(ord(ch) - ord("a") + 1)

        # Apply digit sum transformations k times
        while k > 0:
            digit_sum = 0
            for digit in numeric_string:
                digit_sum += int(digit)
            numeric_string = str(digit_sum)
            k -= 1

        # Convert the final string to integer and return
        return int(numeric_string)

• time: O(k * n)
• space: O(n)

Approach 2: Direct Integer Operation

class Solution:
    def getLucky(self, s: str, k: int) -> int:
        # Convert the string to a number by summing digit values
        current_number = 0
        for ch in s:
            position = ord(ch) - ord("a") + 1
            while position > 0:
                current_number += position % 10
                position //= 10

        # Apply digit sum transformations k-1 times
        for i in range(1, k):
            digit_sum = 0
            while current_number > 0:
                digit_sum += current_number % 10
                current_number //= 10
            current_number = digit_sum

        return current_number

• time: O(n)
• space: O(1)