Leetcode 168. Excel Sheet Column Title

Problem

Given a positive integer, we need to convert it to a column title as it appears in an Excel sheet.

Excel columns follow a pattern similar to the base-26 numeral system, but it is not exactly the same. The main difference is when a number can be exactly divided by 26 in Excel, it will be assigned to 'Z', but in base-26 system, 'Z' means 25. Therefore, while mapping to alphabet letters, we need a mechanism to handle the number which can be divided by 26 correctly.

Let's take a look at an example to understand the problem.

Example

If the input number is 28, it should return the string "AB".

Here, the 'A' correspond to the 27 (26 + 1) and 'B' correspond to 2. When we add 26 and 2, we get 28 which is the input number.

Approach

We will use a recursive strategy to solve this problem.

  1. We decrease the input number, n, by 1 to tackle the numbers which are exactly divided by 26 (if such is the case).
  2. Then we find the remainder of the number divided by 26.
  3. We add 'A' and the remainder to get the corresponding alphabet character.
  4. If the number, n, is not zero then we repeat this process by calling the function again with n = (n - 1) / 26.

We keep repeating these steps until the number n becomes zero.

An ASCII illustration is shown below to understand this in a better way:

1
2
3Input: n=2
4"A" corresponds to 1 (0 + 1)
5"B" corresponds to 2 (0 + 2)
6
7Result: "B"

Python Solution

1
2python
3class Solution:
4    def convertToTitle(self, n: int) -> str:
5        return "" if n == 0 else self.convertToTitle((n - 1) // 26) + chr((n - 1) % 26 + ord('A'))

C# Solution

1
2csharp
3public class Solution {
4    public string ConvertToTitle(int n) {
5        return n == 0 ? "" : ConvertToTitle((n - 1) / 26) + (char)((n - 1) % 26 + 'A');
6    }
7}

Java Solution

1
2java
3public class Solution {
4    public String convertToTitle(int n) {
5        return n == 0 ? "" : convertToTitle((n - 1) / 26) + (char)((n - 1) % 26 + 'A');
6    }
7}

JavaScript Solution

1
2javascript
3var convertToTitle = function(n) {
4    return n === 0 ? '' : convertToTitle(Math.floor((n - 1) / 26)) + String.fromCharCode((n - 1) % 26 + 'A'.charCodeAt(0));
5};

C++ Solution

1
2cpp
3class Solution {
4public:
5    string convertToTitle(int n) {
6        return n == 0 ? "" : convertToTitle((n - 1) / 26) + (char)((n - 1) % 26 + 'A');
7    }
8};

Here, 'A' represents the integer 1, 'B' represents 2, and so on till 'Z' which represents 26. So, for a number n, we calculate (n-1) % 26 which gets us a number between 0 and 25. Adding this to 'A' gives us the character mapping for the column title. We recursively call the function with the parameter (n - 1) / 26 to get the complete title. For example, if the number is 28, the remainder is 2 and (n - 1) / 26 is 1. Therefore, we map 2 to 'B' and call the function with 1 which gives us 'A'. Hence the result is 'AB'.# Use Case

This problem follows the pattern of a base change. For instance, when we convert a binary number to its decimal equivalent, we perform a similar operation, like finding the remainder on division by 2. Therefore, understanding this problem can help us tackle other base change questions.

Another real-world scenario where this problem becomes useful is in creating hashes or labels for large datasets. Instead of labeling the dataset with numbers, which can become large and confusing, we can use this base change technique for labeling.

Additionally, this problem can assist a programmer to understand the ASCII encoding scheme. This problem though being conceptual simple allows a deeper insight in the ASCII encoding scheme, recursion and base change operations.

Conclusion

The conventional numerical representation can sometimes be overwhelming, especially when dealing with large numbers. Excel has a unique way of column representation. It follows a base-26 numeral system where 1 is represented as 'A--', 2 is represented as 'B' and so on until 26 which is represented as 'Z'. However, unlike the base-26 numeral system, excel treats numbers that can be exactly divided by 26 differently.

The method of converting this excel representation to its equivalent numerical system not only involves understanding of recursion but a profound knowledge of ASCII encoding scheme. The above code snippets provide a fair idea of how this conversion can be achieved by recursion and ASCII. The code is implemented in various languages which include Python, C++, Java, JavaScript, and C#.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫