algoadvance

Leetcode 1945. Sum of Digits of String After Convert

Problem Statement

You are given a string s consisting of lowercase English letters, and an integer k.

First, 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). For example, if s = "zbax", then we have to convert it to the integer 261124.

Then, transform the integer by repeating the following process k times:

  1. Replace the integer with the sum of its digits.

Return the resulting integer after performing the above operations k times.

Clarifying Questions

  1. Input Length Constraints: What is the length range of the string s and the value range for k?
    • Constraints are typically such that s can be up to 100 characters and k up to 100.
  2. Edge Cases:
    • What happens if k is 0?
    • Are there any non-lowercase alphabetic inputs?
    • Assume s has only lowercase English letters and k is a positive integer as per constraint definitions.

Strategy

  1. Step 1: Convert String to Integer:
    • Replace each character in the string with its corresponding numeric position in the alphabet.
    • Concatenate these numeric positions to get the initial integer value.
  2. Step 2: Transform the Integer:
    • For k iterations, transform the number by summing its digits.
  3. Sum Digits Function:
    • Create a helper function to obtain the sum of digits of a given integer.

Code

#include <iostream>
#include <string>

int getSumOfDigits(int num) {
    int sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

int getLucky(std::string s, int k) {
    // Step 1: Convert string to number
    std::string numberStr = "";
    for (char c : s) {
        int val = c - 'a' + 1;
        numberStr += std::to_string(val);
    }

    // Convert numberStr to integer for digit summing
    int num = std::stoi(numberStr);

    // Step 2: Sum of digits transformation k times
    for (int i = 0; i < k; ++i) {
        num = getSumOfDigits(num);
    }
    
    return num;
}

int main() {
    std::string s = "zbax";
    int k = 2;
    std::cout << "Result: " << getLucky(s, k) << std::endl; // Output should be 8
    return 0;
}

Time Complexity

  1. String Conversion: O(n) where n is the length of the string s.

  2. Digit Summing (getSumOfDigits): The worst-case number of digits for this problem would be approximately 3 times the length of s (each letter ‘z’ yields “26”). Taking the sum is O(m) where m is the number of digits.

  3. Total Time Complexity: O(n + k * m), where n is the length of s and m is the number of digits in the number formed. Given the constraints, this is efficient enough.

Feel free to ask if you have any further questions or need any modifications.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI