168. Excel Sheet Column Title

Description

The problem is to convert a given positive integer, representing a column number in Excel, into its corresponding column title as it appears in an Excel sheet. For example, the column number 1 corresponds to "A", 28 to "AB", and 701 to "ZY". The goal is to simulate this conversion process and return the correct column title.

Intuition

Excel column titles are similar to a base-26 numeral system, where each digit can be any of the letters 'A' to 'Z'. However, instead of being zero-indexed, this system is one-indexed (i.e., A = 1, B = 2, ... , Z = 26). The challenge is to correctly map the column number to this one-indexed system and build the title by repeatedly determining the remainder and quotient as we would in a numeral system conversion.

Approach

1. Initialization: - Start with an empty string str to accumulate the characters that make up the column title. - Use a loop to repeatedly determine the character that corresponds to the current last digit in the title.
2. Conversion Logic: - For each iteration, calculate the index by taking the remainder of (columnNumber - 1) % 26. This maps 1 to 'A', 2 to 'B', and so on up to 26 for 'Z'. - Append the character corresponding to the current index to the beginning of the result string. - Update the columnNumber by reducing it to the next digit using integer division (columnNumber - 1) / 26.
3. Final Output: - Once the columnNumber is reduced to 0, the loop ends and the complete column title is returned as the output string.

Complexity

Time Complexity:

O(log26(n)), where n is the column number. The number of iterations is proportional to the number of digits in the base-26 representation, which is logarithmic relative to the column number.

Space Complexity:

O(1) additional space is required for the conversion (excluding the space used to store the output string).

Code

C++

class Solution {
public:
    string convertToTitle(int columnNumber) {
        string str = "";
        while (columnNumber > 0) {
            int index = (columnNumber - 1) % 26;
            str = char('A' + index) + str;
            columnNumber = (columnNumber - 1) / 26;
        }
        return str;
    }
};

Python

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        result = ""
        while columnNumber > 0:
            index = (columnNumber - 1) % 26
            result = chr(index + ord('A')) + result
            columnNumber = (columnNumber - 1) // 26
        return result

Java

class Solution {
    public String convertToTitle(int columnNumber) {
        StringBuilder str = new StringBuilder();
        while (columnNumber > 0) {
            int index = (columnNumber - 1) % 26;
            str.insert(0, (char)('A' + index));
            columnNumber = (columnNumber - 1) / 26;
        }
        return str.toString();
    }
}

JavaScript

var convertToTitle = function (columnNumber) {

    const Letter = "ZABCDEFGHIJKLMNOPQRSTUVWXY"
    let str = ""
    while (columnNumber > 0) {
        str = Letter.charAt(columnNumber % 26) + str
        columnNumber -= columnNumber % 26 == 0 ? 26 : columnNumber % 26
        columnNumber /= 26
    }
    return str
};