Problem statement
Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
Problem statement taken from: https://leetcode.com/problems/excel-sheet-column-title
Example 1:
Input: columnNumber = 1
Output: 'A'
Example 2:
Input: columnNumber = 28
Output: 'AB'
Example 3:
Input: columnNumber = 701
Output: 'ZY'
Constraints:
- 1 <= columnNumber <= 2^31 - 1
Explanation
This is one of the easiest problem in LeetCode. We need to follow the below algorithm to get the answer.
- initialize allAlphabets = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
answer = ''
reminder = 0
- loop while columnNumber > 0
- set columnNumber = columnNumber - 1
- set reminder = columnNumber % 26
- update answer.push_back(allAlphabets[reminder])
- update columnNumber = columnNumber / 26
- while end
- reverse(answer.begin(), answer.end())
- return answer
The time complexity of the above approach is O(log26(n)), and the space complexity is O(1).
Let's check our algorithm in C++, Golang, and JavaScript.
C++ solution
class Solution {
public:
string convertToTitle(int columnNumber) {
string allAlphabets = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
string answer = '';
int reminder;
while(columnNumber > 0) {
columnNumber -= 1;
reminder = columnNumber % 26;
answer.push_back(allAlphabets[reminder]);
columnNumber /= 26;
}
reverse(answer.begin(), answer.end());
return answer;
}
};
Golang solution
func convertToTitle(columnNumber int) string {
allAlphabets := 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
answer := ''
reminder := 0
for columnNumber > 0 {
columnNumber -= 1
reminder = columnNumber % 26
answer += string(allAlphabets[reminder])
columnNumber /= 26
}
return reverse(answer)
}
func reverse(s string) string {
runes := []rune(s)
for i, j := 0, len(runes) - 1; i < j; i, j = i + 1, j - 1 {
runes[i], runes[j] = runes[j], runes[i]
}
return string(runes)
}
JavaScript solution
var convertToTitle = function(columnNumber) {
let allAlphabets = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ';
let answer = '';
let reminder;
while(columnNumber > 0) {
columnNumber -= 1;
reminder = columnNumber % 26;
answer += allAlphabets[reminder];
columnNumber = Math.floor(columnNumber / 26);
}
return answer.split('').reverse().join('');
};
Let's dry-run our algorithm to see how the solution works.
Input: columnNumber = 1092
Step 1: allAlphabets = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
answer = ''
reminder = 0
Step 2: loop while columnNumber > 0
1092 > 0
true
columnNumber = columnNumber - 1
= 1092 - 1
= 1091
reminder = columnNumber % 26
= 1091 % 26
= 25
answer.push_back(allAlphabets[reminder])
answer.push_back(allAlphabets[25])
answer.push_back('Z')
answer = 'Z'
columnNumber = columnNumber / 26
= 1091 / 26
= 41
Step 2: loop while columnNumber > 0
41 > 0
true
columnNumber = columnNumber - 1
= 41 - 1
= 40
reminder = columnNumber % 26
= 40 % 26
= 14
answer.push_back(allAlphabets[reminder])
answer.push_back(allAlphabets[14])
answer.push_back('O')
answer = 'ZO'
columnNumber = columnNumber / 26
= 40 / 26
= 1
Step 3: loop while columnNumber > 0
1 > 0
true
columnNumber = columnNumber - 1
= 1 - 1
= 0
reminder = columnNumber % 26
= 0 % 26
= 0
answer.push_back(allAlphabets[reminder])
answer.push_back(allAlphabets[0])
answer.push_back('A')
answer = 'ZOA'
columnNumber = columnNumber / 26
= 1 / 26
= 0
Step 4: loop while columnNumber > 0
0 > 0
false
Step 5: reverse(answer.begin(), answer.end())
answer = 'AOZ'
Step 6: retrun answer
We return the answer as AOZ.
Top comments (0)