We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Digits of String After Convert

Number: 2076

Difficulty: Easy

Paid? No

Companies: Microsoft

Problem Description

Given a string s composed of lowercase English letters and an integer k, convert s to a number by replacing each letter with its alphabetical position (e.g., 'a' becomes 1, 'b' becomes 2, etc.). Concatenate these numbers to form one large number. Then, perform a "digit-sum" transformation on this number k times, where each transformation replaces the number with the sum of its digits. Return the final resulting number.

Key Insights

  • Map each character in s to its corresponding digit value (1-indexed).
  • Concatenate these numerical representations to form an initial number.
  • Repeatedly sum the digits of the current number for k iterations.
  • The transformation rapidly reduces the size of the number, making subsequent digit sums efficient.
  • A simple simulation using string manipulation or arithmetic suffices due to the small input constraints.

Space and Time Complexity

Time Complexity: O(n + k * m), where n is the length of s and m is the number of digits during the transformation (which reduces with each iteration).
Space Complexity: O(m), for storing the intermediate numeric string.

Solution

We first create a numeric string by converting each character in s to its corresponding position in the alphabet. Once we have this large number, we perform k iterations of digit-sum transformation:

  1. Sum the digits of the current number.
  2. Update the number with this sum. We use simple loops and arithmetic or string conversion to perform the digit summing. This approach is straightforward, using basic operations without needing any advanced data structures.

Code Solutions

# Function to perform the conversion and k-digit-sum transformations
def getLucky(s: str, k: int) -> int:
    # Convert s into a numeric string using the mapping (a=1, b=2, ..., z=26)
    num_str = "".join(str(ord(char) - ord('a') + 1) for char in s)
    
    # First transformation: sum the digits of the numeric string
    current_sum = sum(int(ch) for ch in num_str)
    k -= 1  # One transformation has already been performed
    
    # Continue performing transformation k-1 more times
    while k > 0:
        current_sum = sum(int(ch) for ch in str(current_sum))
        k -= 1
    return current_sum

# Example usage:
print(getLucky("iiii", 1))  # Expected Output: 36
← Back to All Questions