Excel Sheet Column Title
Description
A spreadsheet names its columns with letters: A, B and so on to Z, then AA, AB to AZ, BA to ZZ, then AAA, and so on. Given a column's number, columnNumber, return its title.
Column 1 is A, 26 is Z, 27 is AA and 28 is AB.
Examples
Example 1
Input: columnNumber = 1
Output: "A"
Explanation: Column 1 is A.
Example 2
Input: columnNumber = 28
Output: "AB"
Explanation: 28 − 1 = 27 = 1 × 26 + 1: B, then 1 − 1 = 0: A. So AB.
Example 3
Input: columnNumber = 701
Output: "ZY"
Explanation: 701 − 1 = 700 = 26 × 26 + 24: Y, then 26 − 1 = 25: Z. So ZY.
Example 4
Input: columnNumber = 52
Output: "AZ"
Explanation: 52 − 1 = 51 = 1 × 26 + 25: Z, then 1 − 1 = 0: A. So AZ, not the B@ plain base 26 gives.
Constraints
- 1 ≤ columnNumber ≤ 2³¹ − 1
Editorial
Brute Force
Intuition
Count the columns the way a car's odometer counts miles, with wheels that show A to Z. Start at A and step forward one column at a time: the last letter moves on one, a Z wraps back to A and carries into the letter before it, and when every letter was Z, a new A goes in front.
Step-by-Step Explanation
Let's trace Example 2, columnNumber = 28:
- Start at A, column 1.
- Columns 2 to 26: the last letter moves on, B, C and so on to Z.
- Column 27: the Z wraps to A and carries, and with no letter before it a new A goes in front: AA.
- Column 28: the last letter moves on to B: AB.
Count Up One Column at a Time — The title after each step; the letters the step changed are lit.
Algorithm
- Start with the title A.
- Repeat
columnNumber − 1times: from the last letter, turn every Z into A and move left; then move the letter you stopped at on by one, or put an A in front if every letter was Z. - Return the title.
Code
class Solution {
public:
string convertToTitle(int columnNumber) {
string title = "A"; // column 1
for (int step = 1; step < columnNumber; step++) { // to the next column, columnNumber - 1 times
int k = title.size() - 1;
while (k >= 0 && title[k] == 'Z') {
title[k] = 'A'; // Z wraps to A and carries into the letter before
k--;
}
if (k < 0) title.insert(title.begin(), 'A'); // every letter wrapped: one letter more
else title[k]++;
}
return title;
}
};
class Solution:
def convertToTitle(self, columnNumber: int) -> str:
title = ["A"] # column 1
for _ in range(columnNumber - 1): # to the next column, columnNumber - 1 times
k = len(title) - 1
while k >= 0 and title[k] == "Z":
title[k] = "A" # Z wraps to A and carries into the letter before
k -= 1
if k < 0:
title.insert(0, "A") # every letter wrapped: one letter more
else:
title[k] = chr(ord(title[k]) + 1)
return "".join(title)
class Solution {
public String convertToTitle(int columnNumber) {
StringBuilder title = new StringBuilder("A"); // column 1
for (int step = 1; step < columnNumber; step++) { // to the next column, columnNumber - 1 times
int k = title.length() - 1;
while (k >= 0 && title.charAt(k) == 'Z') {
title.setCharAt(k, 'A'); // Z wraps to A and carries into the letter before
k--;
}
if (k < 0) title.insert(0, 'A'); // every letter wrapped: one letter more
else title.setCharAt(k, (char) (title.charAt(k) + 1));
}
return title.toString();
}
}
var convertToTitle = function(columnNumber) {
const title = ["A"]; // column 1
for (let step = 1; step < columnNumber; step++) { // to the next column, columnNumber - 1 times
let k = title.length - 1;
while (k >= 0 && title[k] === "Z") {
title[k] = "A"; // Z wraps to A and carries into the letter before
k--;
}
if (k < 0) title.unshift("A"); // every letter wrapped: one letter more
else title[k] = String.fromCharCode(title[k].charCodeAt(0) + 1);
}
return title.join("");
};
Complexity Analysis
Time Complexity: O(n)
One step per column up to n. Most steps change only the last letter; one in 26 also carries once, one in 676 twice, so the carries add fewer than n / 25 letter changes in all.
Space Complexity: O(log n)
The title itself, at most 7 letters for 2³¹ − 1.
Why This Approach Is Not Efficient
It's right, and it takes a step for every column: about 2.1 billion for the largest, 2,147,483,647. On our judge it ran out of time on the largest tests in C++, Python, Java and JavaScript.
A title is a number written in letters, so the letters can be read off by division, like the digits of a number in any base, one division per letter instead of one step per column. One thing is different: the digits run from 1 to 26, A to Z, and there's no zero.
Optimal Approach - Base 26 With No Zero Digit
Intuition
Read the title off from the right, the way you'd read digits. In ordinary base 26, with digits 0 to 25, n % 26 would be the last digit and n / 26 the rest. Here the digits run 1 to 26, so take 1 off first: then (n − 1) % 26 says how far the last letter is from A (0 for A, 25 for Z), and (n − 1) / 26 is the number the letters before it spell. Repeat until nothing is left, putting each new letter in front.
Step-by-Step Explanation
Let's trace Example 3, columnNumber = 701:
701 − 1 = 700:700 % 26 = 24is Y, and700 / 26 = 26is left.26 − 1 = 25:25 % 26 = 25is Z, and25 / 26 = 0is left.- Nothing is left, so the title is ZY.
Take 1 Off, Then Divide by 26 — The title as it grows; the letter just put in front is lit.
Algorithm
- Start with an empty title.
- While
n > 0: take 1 offn, put the letter'A' + n % 26in front of the title, and setnton / 26. - Return the title.
Code
class Solution {
public:
string convertToTitle(int columnNumber) {
string title;
int n = columnNumber;
while (n > 0) {
n--; // 1 to 26 become 0 to 25: there's no zero digit
title = char('A' + n % 26) + title; // the last letter goes in front
n /= 26; // what the letters before it spell
}
return title;
}
};
class Solution:
def convertToTitle(self, columnNumber: int) -> str:
title = ""
n = columnNumber
while n > 0:
n -= 1 # 1 to 26 become 0 to 25: there's no zero digit
title = chr(ord("A") + n % 26) + title # the last letter goes in front
n //= 26 # what the letters before it spell
return title
class Solution {
public String convertToTitle(int columnNumber) {
StringBuilder title = new StringBuilder();
int n = columnNumber;
while (n > 0) {
n--; // 1 to 26 become 0 to 25: there's no zero digit
title.insert(0, (char) ('A' + n % 26)); // the last letter goes in front
n /= 26; // what the letters before it spell
}
return title.toString();
}
}
var convertToTitle = function(columnNumber) {
let title = "";
let n = columnNumber;
while (n > 0) {
n--; // 1 to 26 become 0 to 25: there's no zero digit
title = String.fromCharCode(65 + n % 26) + title; // the last letter goes in front
n = Math.floor(n / 26); // what the letters before it spell
}
return title;
};
Complexity Analysis
Time Complexity: O(log n)
One letter per pass, and each pass divides n by 26: 7 passes for the largest column, whose title is FXSHRXW.
Space Complexity: O(1)
Just n and the title being built; the title is the answer.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Reading it as plain base 26. chr(ord("A") + n % 26 - 1)
On columnNumber = 26 it returns "A@"; the answer is "Z". Taking n % 26 as the letter treats the digits as 0 to 25, but a column has no 0 digit: 26 gives a remainder of 0 and there's no letter for it. Take 1 off before each digit, so 1 to 26 become 0 to 25.
Writing Z for a 0 without borrowing. "Z" if r == 0
On columnNumber = 52 it returns "BZ"; the answer is "AZ". A remainder of 0 means the letter is Z, and that Z used up 26 of what's left: the quotient must drop by one. Without the borrow, 26 comes out AZ, 52 BZ and 702 AAZ.
Putting the letters in the order they come off. title += chr(ord("A") + n % 26)
On columnNumber = 28 it returns "BA"; the answer is "AB". The first letter the loop finds is the last one of the title, the rightmost. Appending puts it first: 28 comes out BA instead of AB. Each new letter goes in front.
Where This Pattern Is Taught
This problem practises a base with no zero digit: take 1 off before each digit, then % 26 picks the letter and / 26 the rest. It's taught in Digits and Number Manipulation.