
Description
The problem is to convert a given positive integer, representing a column number in Excel, into its corresponding column title as it appears in an Excel sheet. For example, the column number 1
corresponds to "A"
, 28
to "AB"
, and 701
to "ZY"
. The goal is to simulate this conversion process and return the correct column title.
Intuition
Excel column titles are similar to a base-26 numeral system, where each digit can be any of the letters 'A'
to 'Z'
. However, instead of being zero-indexed, this system is one-indexed (i.e., A = 1
, B = 2
, ... , Z = 26
). The challenge is to correctly map the column number to this one-indexed system and build the title by repeatedly determining the remainder and quotient as we would in a numeral system conversion.
Approach
- Initialization:
- Start with an empty string
str
to accumulate the characters that make up the column title. - Use a loop to repeatedly determine the character that corresponds to the current last digit in the title. - Conversion Logic:
- For each iteration, calculate the index by taking the remainder of
(columnNumber - 1) % 26
. This maps1
to'A'
,2
to'B'
, and so on up to26
for'Z'
. - Append the character corresponding to the current index to the beginning of the result string. - Update thecolumnNumber
by reducing it to the next digit using integer division(columnNumber - 1) / 26
. - Final Output:
- Once the
columnNumber
is reduced to0
, the loop ends and the complete column title is returned as the output string.
Complexity
Time Complexity:
O(log26(n))
, where n
is the column number. The number of iterations is proportional to the number of digits in the base-26 representation, which is logarithmic relative to the column number.
Space Complexity:
O(1)
additional space is required for the conversion (excluding the space used to store the output string).
Code
C++
class Solution {
public:
string convertToTitle(int columnNumber) {
string str = "";
while (columnNumber > 0) {
int index = (columnNumber - 1) % 26;
str = char('A' + index) + str;
columnNumber = (columnNumber - 1) / 26;
}
return str;
}
};
Python
class Solution:
def convertToTitle(self, columnNumber: int) -> str:
result = ""
while columnNumber > 0:
index = (columnNumber - 1) % 26
result = chr(index + ord('A')) + result
columnNumber = (columnNumber - 1) // 26
return result
Java
class Solution {
public String convertToTitle(int columnNumber) {
StringBuilder str = new StringBuilder();
while (columnNumber > 0) {
int index = (columnNumber - 1) % 26;
str.insert(0, (char)('A' + index));
columnNumber = (columnNumber - 1) / 26;
}
return str.toString();
}
}
JavaScript
var convertToTitle = function (columnNumber) {
const Letter = "ZABCDEFGHIJKLMNOPQRSTUVWXY"
let str = ""
while (columnNumber > 0) {
str = Letter.charAt(columnNumber % 26) + str
columnNumber -= columnNumber % 26 == 0 ? 26 : columnNumber % 26
columnNumber /= 26
}
return str
};