Excel Sheet Column Title LeetCode Solution

Difficulty Level Easy
Frequently asked in Adobe Amazon Apple Facebook Goldman Sachs Google Microsoft Oracle Paytm Uber VMware ZenefitsViews 1757

Problem Statement

Excel Sheet Column Title LeetCode Solution – We are given a column number (let’s call it colNum) and need to 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

Examples

Example 1:

Input: columnNumber = 1
Output: "A"

Example 2:

Input: columnNumber = 28
Output: "AB"

Example 3:

Input: columnNumber = 701
Output: "ZY"

Approach

consider the letter ‘A’ to have a value of 1, ‘B’->2 ….. ‘Z’->26
note that in the above notation, values are 1-based

here our Radix (R) == 26

the final value of a number X Y Z = X * R^2 + Y * R + Z

this looks similar to base-10 decimal number but the biggest difference is that the numbers on every digit starts with 1, instead of 0., and the max on each digit goes up to R (Radix) instead of R-1

for example
Z== Radix
then next number is AA = R + 1 = Z+1
ZZ = R * R + R
next number is AAA = 1*R^2 + 1 * R + 1 = ZZ +1

so from the AAA notation to their sequence number (decimal) it’s easy, but the other way is a bit tricky due to the way % and / operates

As we can observe from the given example above, after columnNumber 26, the answer is obtained by repetitive adding letters corresponding to (columnNumber-1)%26. We can argue its correctness by the principle of induction. To understand how the algorithm is working let us take an example where the given number is 28.

Let us assume our answer “res” string to be empty. Since in the char system, A is 0 but in excel it is 1, we will decrement the value of columnNumber and take colNum%26.

Before Iteration: colNum (given) = 28

First Iteration
colNum = colNum - 1 = 28- 1 = 27
t = 'A' + (27)%26 = 'A' + 1 = 'B'
res = t + res = 'B'
colNum /= 26 = 27/26 = 1
Second Iteration
colNum = colNum - 1 = 1 - 1 = 0
t = 'A' + 0%26 = 'A'
res = ‘A’ + 'B' = ‘AB’
colNum = colNum/26 = 1/26 = 0

After the second iteration, colNum becomes 0, and hence loop stops, and we get the answer as “res”.

Code

C++ Code for Excel Sheet Column Title LeetCode

class Solution {
public:
    string convertToTitle(int colNum) {
        string res = "";
        char t;
        while(colNum) {
            t = 'A' + (--colNum)%26;
            res = t + res;
            colNum /= 26;
        }
        return res;
    }
};

Java Code for Excel Sheet Column Title LeetCode

class Solution {
    public String convertToTitle(int colNum) {
        StringBuilder res = new StringBuilder();
        while(colNum > 0){
            int t = (--colNum)%26;
            colNum /= 26;
            res.append((char)(t+'A'));
        }
        return res.reverse().toString();
    }
}

Complexity Analysis for Excel Sheet Column Title Leetcode Solution

  • Time Complexity: O(log(colNum))
    • everytime, the colNum gets divided by 26, hence O(log(colNum))
  • Space Complexity: O(1)
    • No extra space is required other than res and t, hence O(1)

Reference: https://en.wikipedia.org/wiki/Spreadsheet

Translate »