Hey Guys!, It's day 80 and today we are going to solve today's leetcode problem.
Problem: 168. Excel Sheet Column Title
Given an integer columnNumber
, return its corresponding column title as it appears in an Excel sheet.
Example 1:
Input: columnNumber = 1
Output: "A"
Example 2:
Input: columnNumber = 28
Output: "AB"
Example 3:
Input: columnNumber = 701
Output: "ZY"
Problem Understanding:
- In this problem, we are given an integer representing a column number.
- The task is to return its corresponding column title as it appears in an Excel sheet, where the letters range from A to Z for the numbers 1 to 26, and then AA to AZ, BA to BZ, and so on.
- For instance, given the input 28, the output should be "AB".
Approaches:
Iterative Approach:
- Initialize an empty string ans to store the resulting column title.
- Use a while loop that continues until the columnNumber becomes 0.
- Inside the loop, subtract 1 from the columnNumber to adjust for the 1-based indexing of the English alphabet.
- Calculate the remainder of columnNumber divided by 26 and add the corresponding letter to the ans string.
- Update columnNumber by dividing it by 26.
- Continue the loop until columnNumber becomes 0.
Code:
string convertToTitle(int columnNumber) {
string ans = "";
while (columnNumber) {
columnNumber--;
char c = 'A' + columnNumber % 26;
result = c + result;
columnNumber /= 26;
}
return result;
}
Recursive Approach:
- Base Case: If the columnNumber is 0, an empty string is returned, signifying the end of the recursion.
Inside the recursive function:
- Subtract 1 from the columnNumber to adjust for the 1-based indexing of the English alphabet.
- Calculate the remainder of columnNumber divided by 26 and convert it to the corresponding letter.
- Recursively call the function with the updated columnNumber divided by 26.
- Append the calculated letter to the result of the recursive call.
- The recursion continues until the base case is reached.
Code:
string convertToTitle(int columnNumber) {
if (columnNumber == 0) return "";
columnNumber--;
char c = 'A' + columnNumber % 26;
return convertToTitle(columnNumber / 26) + c;
}
Complexity Analysis:
Complexity | Notation | Explanation |
---|---|---|
Time(Recursion) | O(log N) | Exponential Approach |
Space(Recursion) | O(log N) | The algorithm uses a logN recursive stack |
Complexity | Notation | Explanation |
---|---|---|
Time(Iterative) | O(log N) | Exponential Approach |
Space(Iterative) | O(1) | The algorithm uses a constant extra space |
Top comments (0)