# LeetCode 168: Excel Sheet Column Title ## Problem Restatement We are given a positive integer: ```python columnNumber ``` We need to return the corresponding Excel column title. Excel columns are labeled like this: | Number | Title | |---:|---| | `1` | `"A"` | | `2` | `"B"` | | `26` | `"Z"` | | `27` | `"AA"` | | `28` | `"AB"` | | `701` | `"ZY"` | The problem asks us to convert an integer into this Excel-style column label. The constraint is `1 <= columnNumber <= 2^31 - 1`. ## Input and Output | Item | Meaning | |---|---| | Input | Positive integer `columnNumber` | | Output | Excel column title as a string | | Alphabet | Uppercase letters `A` through `Z` | | Important detail | There is no zero digit | Example function shape: ```python def convertToTitle(columnNumber: int) -> str: ... ``` ## Examples Example 1: ```python columnNumber = 1 ``` Output: ```python "A" ``` Example 2: ```python columnNumber = 26 ``` Output: ```python "Z" ``` Example 3: ```python columnNumber = 28 ``` The title is: ```python "AB" ``` Example 4: ```python columnNumber = 701 ``` The title is: ```python "ZY" ``` ## First Thought: Base 26 This looks like base conversion. In normal base 26, digits would be: ```text 0, 1, 2, ..., 25 ``` But Excel columns use: ```text A, B, C, ..., Z ``` where: ```text A = 1 B = 2 ... Z = 26 ``` There is no digit for zero. That means this is not ordinary base 26. It is a 1-indexed, or bijective, base-26 system. The fix is simple: subtract `1` before taking modulo `26`. ## Key Insight For each character, do: ```python columnNumber -= 1 remainder = columnNumber % 26 ``` Now the remainder is between `0` and `25`. We can map it to a letter: ```python 0 -> "A" 1 -> "B" ... 25 -> "Z" ``` Then divide by `26`: ```python columnNumber //= 26 ``` This extracts the title from right to left. So we collect characters, then reverse them at the end. ## Why We Subtract One Consider: ```python columnNumber = 26 ``` If we use normal modulo: ```python 26 % 26 = 0 ``` That would suggest `"A"` if we mapped `0` to `"A"`, which is wrong. The answer should be `"Z"`. So before modulo, use: ```python columnNumber -= 1 ``` Now: ```python 25 % 26 = 25 ``` and `25` maps to `"Z"`. This same trick also handles `27`: ```python 27 - 1 = 26 26 % 26 = 0 -> "A" 26 // 26 = 1 1 - 1 = 0 0 % 26 = 0 -> "A" ``` Collected from right to left, this gives: ```python "AA" ``` ## Algorithm Initialize an empty list: ```python chars = [] ``` While `columnNumber > 0`: 1. Subtract `1` from `columnNumber`. 2. Compute `columnNumber % 26`. 3. Convert that remainder to a letter. 4. Append the letter to `chars`. 5. Divide `columnNumber` by `26`. Finally, reverse `chars` and join it. ## Walkthrough Use: ```python columnNumber = 28 ``` First iteration: ```python columnNumber -= 1 # 27 remainder = 27 % 26 # 1 letter = "B" columnNumber = 27 // 26 # 1 ``` Collected: ```python ["B"] ``` Second iteration: ```python columnNumber -= 1 # 0 remainder = 0 % 26 # 0 letter = "A" columnNumber = 0 // 26 # 0 ``` Collected: ```python ["B", "A"] ``` Reverse: ```python ["A", "B"] ``` Return: ```python "AB" ``` ## Correctness The algorithm repeatedly extracts the last Excel digit. Before each modulo operation, it subtracts `1`, converting Excel’s 1-based digit system into a 0-based range from `0` to `25`. The remainder then uniquely determines the last letter of the current title. After extracting that letter, integer division by `26` removes the last Excel digit and leaves the remaining prefix to be processed. The loop continues until no prefix remains. Because digits are extracted from right to left, reversing the collected letters gives the title in the correct left-to-right order. Therefore, the algorithm returns the correct Excel column title. ## Complexity Let `k` be the number of letters in the output. | Metric | Value | Why | |---|---|---| | Time | `O(k)` | Each loop produces one letter | | Space | `O(k)` | We store the output letters | Since `columnNumber` is at most `2^31 - 1`, `k` is small. ## Implementation ```python class Solution: def convertToTitle(self, columnNumber: int) -> str: chars = [] while columnNumber > 0: columnNumber -= 1 remainder = columnNumber % 26 chars.append(chr(ord("A") + remainder)) columnNumber //= 26 chars.reverse() return "".join(chars) ``` ## Code Explanation Create a list to store letters: ```python chars = [] ``` The loop runs until the whole number has been converted: ```python while columnNumber > 0: ``` Convert from 1-based Excel digits to 0-based modulo digits: ```python columnNumber -= 1 ``` Find the current letter index: ```python remainder = columnNumber % 26 ``` Convert it to a character: ```python chars.append(chr(ord("A") + remainder)) ``` Move to the next higher digit: ```python columnNumber //= 26 ``` The letters were collected from right to left, so reverse them: ```python chars.reverse() ``` Return the final title: ```python return "".join(chars) ``` ## Recursive Implementation The same logic can be written recursively: ```python class Solution: def convertToTitle(self, columnNumber: int) -> str: if columnNumber == 0: return "" columnNumber -= 1 prefix = self.convertToTitle(columnNumber // 26) current = chr(ord("A") + columnNumber % 26) return prefix + current ``` The iterative version is usually preferable because it avoids recursion overhead. ## Testing ```python def run_tests(): sol = Solution() assert sol.convertToTitle(1) == "A" assert sol.convertToTitle(2) == "B" assert sol.convertToTitle(26) == "Z" assert sol.convertToTitle(27) == "AA" assert sol.convertToTitle(28) == "AB" assert sol.convertToTitle(52) == "AZ" assert sol.convertToTitle(53) == "BA" assert sol.convertToTitle(701) == "ZY" assert sol.convertToTitle(702) == "ZZ" assert sol.convertToTitle(703) == "AAA" print("all tests passed") run_tests() ``` | Test | Why | |---|---| | `1` | First column | | `26` | End of one-letter range | | `27` | First two-letter title | | `28` | Standard example | | `52` | Ends with `Z` | | `53` | Carries into next leading letter | | `701` | Standard larger example | | `702` | `"ZZ"` boundary | | `703` | First three-letter title |