Excel Sheet Column Title Leetcode Solution


Difficulty Level Easy
Frequently asked in Adobe Google
Math Number System

Problem Statement

In this problem a positive integer is given which represents a column number of an Excel sheet, we have to return its corresponding column title as appear in an Excel sheet.

Excel Sheet Column Title Leetcode Solution

Example

#1

28
"AB"

#2

701
"ZY"

Approach

This problem is the reverse of the problem in which we have to find out the column number from a column title.
So in that problem we converted a base-26 number into base-10 number which is a decimal number. In this problem we have to find out column title from column number. So here we just have to do opposite, i.e. we have to convert a base-10 (decimal) number into a number of base-26 system.

We know in general number system of suppose base-26 should have 26 characters which represents values 0 to 25. But in Excel sheet column title this is little different. It represents values from 1 to 26. So if we use characters A-Z as 0-25, then it will look like below equation:

Let string be ABZ, this is corresponding to number n:
n = (A+1) * 26^2 + (B+1) * 26^1 + (Z+1) * 26^0

Why (A+1)? Because in char system ‘A’ is 0, but in excel system ‘A’ is one. Every char get an extra one.

So in order to get last char i.e. Z we would first minus 1 i.e. n– and then get n%26
(n-1)%26 = Z
Now divide with 26 and repeat same process for next character.
(n-1)/26 = (A+1) * 26^1 + (B+1) * 26^0

Algorithm

  1. Create an empty string for storing the characters.
  2. Run a loop while n is positive.
    • Subtract 1 from n.
    • Get current character by doing modulo of  n by 26.
    • Divide n by 26.
  3. Now reverse the result string because we have found characters from right to left.
  4. Return the reversed string.

Implementation

C++ Program for Excel Sheet Column Title Leetcode Solution

#include <bits/stdc++.h>
using namespace std;

string convertToTitle(int n) 
{        
    string ans;
    while(n>0)
    {
        --n;
        int d= n%26;
        n/=26;
        ans+= 'A'+d;            
    }
   reverse(ans.begin(),ans.end());
   return ans; 
}

int main() 
{
   cout<<convertToTitle(28) <<endl;
   return 0; 
}
AB

Java Program for Excel Sheet Column Title Leetcode Solution

class Rextester{
    
    public static String convertToTitle(int n) 
    {
        StringBuilder ans= new StringBuilder();
        while(n>0)
        {
            --n;
            int d= n%26;
            n/=26;
            ans.append((char)('A'+d));            
        }
        ans.reverse();
        return ans.toString(); 
    }
    
    public static void main(String args[])
    {    	
       System.out.println( convertToTitle(28)  ) ;
    }
}
AB

Complexity Analysis for Excel Sheet Column Title Leetcode Solution

Time Complexity

O(log(n)) : Where n is the given column number. We are dividing the number by 26 in each iteration, hence time complexity will be O(log(n)).

Space Complexity 

O(1) : We are not using any extra space other than for storing the result.