
Description
Given a string s
consisting of lowercase English letters, you first convert each letter to its position in the alphabet (e.g., 'a' -> 1
, 'b' -> 2
, etc.). Then you concatenate these numbers to form a single number. After that, you perform a transformation k
times where, in each transformation, you replace the number with the sum of its digits. The goal is to return the resulting number after k
transformations.
Intuition
The problem requires two main operations:
- Converting characters to their corresponding numeric values.
- Summing the digits of a number multiple times.
The key observation is that the transformation reduces the number's size in each step, making it more manageable after a few iterations. The repetitive nature of summing digits is an indicator that the problem can be solved efficiently even with multiple iterations.
Approach
- Convert the String: Start by converting each character in the string
s
to its corresponding position in the alphabet. Concatenate these values to form a large number in string format. - Sum the Digits: Perform the transformation
k
times, where each transformation involves summing the digits of the current number and updating the number to this sum. - Return the Result: After
k
transformations, the number will be reduced to a single-digit or small number, which is returned as the final result.
Complexity
Time Complexity:
- The initial conversion of the string
s
to its numeric form isO(n)
, wheren
is the length ofs
. - Each transformation to sum the digits is
O(m)
, wherem
is the number of digits in the current number. Givenk
transformations, the total complexity isO(n + k * m)
.
Space Complexity:
O(1)
if we consider only the extra space for storing numeric values, since all operations are done in place (excluding the input and output).
Code
C++
class Solution {
public:
int getLucky(string s, int k) {
string value = "";
for (char c : s) {
value += to_string(c - 'a' + 1);
}
while (k-- > 0) {
int v = 0;
for (char c : value) {
v += c - '0';
}
value = to_string(v);
}
return stoi(value);
}
};
Python
class Solution:
def getLucky(self, s: str, k: int) -> int:
value = ''.join(str(ord(c) - 96) for c in s)
while k > 0:
v = sum(int(digit) for digit in value)
value = str(v)
k -= 1
return int(value)
Java
class Solution {
public int getLucky(String s, int k) {
StringBuilder value = new StringBuilder();
for (char c : s.toCharArray()) {
value.append(c - 'a' + 1);
}
while (k-- > 0) {
int v = 0;
for (char c : value.toString().toCharArray()) {
v += Character.getNumericValue(c);
}
value = new StringBuilder(String.valueOf(v));
}
return Integer.parseInt(value.toString());
}
}
JavaScript
var getLucky = function (s, k) {
let value = '';
for (i = 0; i < s.length; i++) {
value += s.charCodeAt(i) - 96
}
do {
let v = 0
for (i = 0; i < value.length; i++)
v += Number(value[i])
value = v.toString();
k--;
} while (k > 0);
return value;
};