168. Excel Sheet Column Title
Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 31.9%
Problem Breakdown
The problem requires converting an integer columnNumber into its corresponding column title as it appears in an Excel sheet. The mapping starts with A -> 1, B -> 2, …, Z -> 26, and continues with AA -> 27, AB -> 28, etc.
Inputs:
- An integer
columnNumber(1 <= columnNumber <= 2^31 - 1)
Outputs:
- A string representing the Excel sheet column title
Implicit Constraints or Tricky Edge Cases:
- The input is always a positive integer.
- The output should be in uppercase letters.
- The conversion involves a base-26 numeral system, but with ‘A’ as 1 instead of 0.
Intuition
The brute-force approach would involve iterating through all possible column titles until reaching the given columnNumber, which is inefficient due to its linear time complexity. A more efficient approach leverages the properties of the base-26 numeral system used in Excel columns, where each letter represents a power of 26.
The key insight is that this problem can be solved using a modified base conversion algorithm. Since ‘A’ corresponds to 1 instead of 0, we need to adjust our calculations by subtracting 1 before performing the modulus and division operations.
Approach
- Initialize an empty string
resultto build the column title. - While
columnNumberis greater than 0:- Subtract 1 from
columnNumberto align with base-26 conversion where ‘A’ = 1. - Calculate the remainder of
columnNumberdivided by 26, which gives the index of the current character in the alphabet (0 for ‘A’, 1 for ‘B’, …, 25 for ‘Z’). - Convert this index to the corresponding character and prepend it to
result. - Update
columnNumberby performing integer division by 26.
- Subtract 1 from
- Return the built
result.
Complexity Analysis
- Time Complexity: O(log_26(n)), where n is the input
columnNumber. This is because we are effectively reducing the number of digits in base-26 representation with each iteration. - Space Complexity: O(1) for the additional variables used, excluding the space required for the output string.
Solution
def convertToTitle(columnNumber: int) -> str:
result = ""
while columnNumber > 0:
columnNumber -= 1 # Adjust for base-26 where 'A' is 1
index = columnNumber % 26
result = chr(index + ord('A')) + result
columnNumber //= 26
return result
Edge Cases Handled
- Minimum Input (1): Converts to “A”.
- Maximum Input (2^31 - 1): Handles the largest possible input without overflow.
- Single Letter Columns (1-26): Directly maps to ‘A’-‘Z’.
- Multi-letter Columns (27+): Correctly handles cases like “AA”, “AB”, …, “FXSHRXW”.