DAY 80 - 168. Excel Sheet Column Title

Nayan Pahuja - Aug 22 '23 - - Dev Community

Hey Guys!, It's day 80 and today we are going to solve today's leetcode problem.

Problem: 168. Excel Sheet Column Title

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

Example 1:

Input: columnNumber = 1
Output: "A"

Example 2:

Input: columnNumber = 28
Output: "AB"

Example 3:

Input: columnNumber = 701
Output: "ZY"


Problem Understanding:

  • In this problem, we are given an integer representing a column number.
  • The task is to return its corresponding column title as it appears in an Excel sheet, where the letters range from A to Z for the numbers 1 to 26, and then AA to AZ, BA to BZ, and so on.
  • For instance, given the input 28, the output should be "AB".

Approaches:

Iterative Approach:

  • Initialize an empty string ans to store the resulting column title.
  • Use a while loop that continues until the columnNumber becomes 0.
  • Inside the loop, subtract 1 from the columnNumber to adjust for the 1-based indexing of the English alphabet.
  • Calculate the remainder of columnNumber divided by 26 and add the corresponding letter to the ans string.
  • Update columnNumber by dividing it by 26.
  • Continue the loop until columnNumber becomes 0.

Code:

string convertToTitle(int columnNumber) {
        string ans = "";
        while (columnNumber) {
            columnNumber--;
            char c = 'A' + columnNumber % 26;
            result = c + result;
            columnNumber /= 26;
        }
        return result;
    }


Enter fullscreen mode Exit fullscreen mode

Recursive Approach:

  • Base Case: If the columnNumber is 0, an empty string is returned, signifying the end of the recursion.

Inside the recursive function:

  • Subtract 1 from the columnNumber to adjust for the 1-based indexing of the English alphabet.
  • Calculate the remainder of columnNumber divided by 26 and convert it to the corresponding letter.
  • Recursively call the function with the updated columnNumber divided by 26.
  • Append the calculated letter to the result of the recursive call.
  • The recursion continues until the base case is reached.

Code:

string convertToTitle(int columnNumber) {
        if (columnNumber == 0) return "";
        columnNumber--;
        char c = 'A' + columnNumber % 26;
        return convertToTitle(columnNumber / 26) + c;
    }

Enter fullscreen mode Exit fullscreen mode

Complexity Analysis:

Complexity Notation Explanation
Time(Recursion) O(log N) Exponential Approach
Space(Recursion) O(log N) The algorithm uses a logN recursive stack
Complexity Notation Explanation
Time(Iterative) O(log N) Exponential Approach
Space(Iterative) O(1) The algorithm uses a constant extra space
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .