grid47 Exploring patterns and algorithms
Oct 21, 2024
4 min read
Solution to LeetCode 168: Excel Sheet Column Title Problem
Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.
Problem
Approach
Steps
Complexity
Input: The input consists of an integer columnNumber, which represents the column number to be converted to Excel column title.
Example: columnNumber = 27
Constraints:
• 1 <= columnNumber <= 2^31 - 1
Output: The output should be a string representing the column title corresponding to the input columnNumber.
Example: Output: 'AA'
Constraints:
• The output is a valid Excel column title.
Goal: The goal is to find the Excel column title corresponding to a given integer columnNumber.
Steps:
• Reduce the columnNumber by 1 (to make the conversion zero-indexed).
• Calculate the remainder when divided by 26, and map it to the corresponding alphabet (A-Z).
• Update columnNumber by dividing it by 26, and continue the process until columnNumber becomes 0.
Goal: The input columnNumber is within a valid range, and the conversion should correctly map the number to its column title.
Steps:
• 1 <= columnNumber <= 2^31 - 1
Assumptions:
• The column number will always have a valid corresponding Excel column title.
• Input: columnNumber = 27
• Explanation: The column title corresponding to 27 is 'AA'. This is because after reducing 27 by 1, we get 26, which corresponds to 'Z'. Dividing by 26 gives us 1, which corresponds to 'A'.
Approach: We will convert the integer columnNumber into its corresponding Excel column title by repeatedly calculating remainders and mapping them to characters.
Observations:
• The problem involves repeatedly dividing the number by 26 and mapping the result to a letter in the alphabet.
• This problem can be solved by simulating the conversion process using basic modular arithmetic.
Steps:
• Initialize an empty string to store the result.
• Iterate while columnNumber is greater than 0.
• In each iteration, calculate the remainder of columnNumber - 1 divided by 26, which gives the corresponding letter.
• Append the letter to the result string.
• Update columnNumber by dividing it by 26.
Empty Inputs:
• The problem guarantees that columnNumber will be at least 1, so no need to handle empty inputs.
Large Inputs:
• For large columnNumbers, the solution must handle the division and string construction efficiently.
Special Values:
• If columnNumber is 1, the result should be 'A'.
Constraints:
• The approach should work efficiently for values up to 2^31 - 1.
string convertToTitle(int columnNumber) {
string res ="";
int mod;
while(columnNumber >0) {
mod =--columnNumber %26;
char x = ('A'+ mod);
res = x + res;
columnNumber /=26;
}
return res;
}
1 : Function Definition
string convertToTitle(int columnNumber) {
Define the function 'convertToTitle' that converts an integer column number to its corresponding Excel column title (e.g., 1 -> 'A').
2 : Variable Initialization
string res ="";
Initialize an empty string 'res' to build the resulting column title as we compute it.
3 : Variable Declaration
int mod;
Declare an integer 'mod' to store the result of the modulo operation, which will be used to calculate the characters of the column title.
4 : While Loop
while(columnNumber >0) {
Start a while loop that continues until 'columnNumber' becomes zero, which means we have processed all digits of the title.
5 : Modulo Operation
mod =--columnNumber %26;
Decrement 'columnNumber' by 1 to handle the 'A' as 0 case, then compute the remainder when dividing by 26 to get the corresponding character's index.
6 : Character Conversion
char x = ('A'+ mod);
Convert the calculated remainder ('mod') to the corresponding character in the alphabet by adding it to the ASCII value of 'A'.
7 : String Update
res = x + res;
Prepend the character 'x' to the result string 'res', so that the title is built in the correct order from right to left.
8 : Column Division
columnNumber /=26;
Divide 'columnNumber' by 26 to move to the next significant digit of the Excel column title.
9 : Return Statement
return res;
Return the computed column title stored in the 'res' string.
Best Case: O(log(columnNumber))
Average Case: O(log(columnNumber))
Worst Case: O(log(columnNumber))
Description: The time complexity is O(log(columnNumber)) because we divide columnNumber by 26 in each iteration.
Best Case: O(1)
Worst Case: O(log(columnNumber))
Description: The space complexity is O(log(columnNumber)) due to the string being built in the result.
