algoadvance

Given a positive integer, convert it to its corresponding column title as it would appear in an Excel sheet. For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB
    ...

Clarifying Questions

  1. Input Constraints:
    • What is the maximum value for the input integer? (As large as a typical integer can be in Python)
  2. Output Format:
    • Should the output strictly be in uppercase? (Yes, as shown in the example)
  3. Edge Cases:
    • Does the program need to handle minimum input (i.e., 1, which should return “A”)?
    • What should be returned for large values, for instance, integer values corresponding to multiple-letter column titles like “ZZZ”?

Strategy

  1. Understanding the Mapping:
    • Excel columns are essentially a base-26 numeral system, where ‘A’ represents 1, ‘B’ represents 2, …, and ‘Z’ represents 26, then ‘AA’ represents 27, in a manner similar to how numbers work in the decimal (base-10) system.
  2. Algorithm:
    • We will use a while loop to continuously divide the number by 26 and find the remainder.
    • Instead of 0-25 (which are typical indices in base 26), we consider 1-26. So each time we reduce the number by 1 to convert between the 1-based index (Excel columns) and the 0-based index (Python characters).
  3. Steps:
    • Initialize an empty list to collect characters.
    • Use a while loop to derive characters by repeatedly reducing the number, converting it to the corresponding character, and concatenating the results.
    • Convert collected characters to a string by joining them in reverse order (since the least significant digit is derived first in the process).

Code

Here is the Python code that performs the above steps:

def convertToTitle(columnNumber: int) -> str:
    result = []
    while columnNumber > 0:
        columnNumber -= 1  # Adjust to make it 0-based.
        remainder = columnNumber % 26
        result.append(chr(remainder + ord('A')))
        columnNumber //= 26
    
    return ''.join(result[::-1])

# Testing the function
print(convertToTitle(1))  # Output: "A"
print(convertToTitle(28))  # Output: "AB"
print(convertToTitle(701))  # Output: "ZY"
print(convertToTitle(702))  # Output: "ZZ"
print(convertToTitle(703))  # Output: "AAA"

Time Complexity

The function efficiently handles converting a large integer to its corresponding Excel column title through a mathematical approach based on properties of the base-26 numeral system.

Try our interview co-pilot at AlgoAdvance.com