# Excel Sheet Column Title **Difficulty:** EASY [External](https://leetcode.com/problems/excel-sheet-column-title) Canonical: https://scaleengineer.com/dsa/problems/excel-sheet-column-title **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math) **Data structures:** String **Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Oracle](https://scaleengineer.com/companies/oracle), [Zoho](https://scaleengineer.com/companies/zoho), [Zenefits](https://scaleengineer.com/companies/zenefits), [Yext](https://scaleengineer.com/companies/yext) --- ## Problem Given an integer `columnNumber`, return _its corresponding column title as it appears in an Excel sheet_. For example: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... **Example 1:** **Input:** columnNumber = 1 **Output:** "A" **Example 2:** **Input:** columnNumber = 28 **Output:** "AB" **Example 3:** **Input:** columnNumber = 701 **Output:** "ZY" **Constraints:** * `1 <= columnNumber <= 231 - 1` # Approaches ## Recursive Approach This approach treats the problem as a base conversion from base-10 to a modified base-26 system. A recursive function is a natural way to implement this. The key insight is that this isn't a standard base-26 system (with digits 0-25), but one with digits 1-26. To handle this, we can convert the number to a 0-indexed system at each step by subtracting 1 before performing the modulo and division operations. The function calculates the rightmost character and then calls itself to find the prefix. **Time:** O(log_{26}(N)) · **Space:** O(log_{26}(N)) **Pros:** The code is very concise and elegant.; It directly models the mathematical recurrence relation of the problem. **Cons:** Incurs overhead from recursive function calls, which can be slightly slower than an iterative solution.; For extremely large inputs (beyond the problem's constraints), it could risk a stack overflow error. ### Explanation The function `convertToTitle(n)` works as follows: If `n` is 0, it returns an empty string, which is our base case. Otherwise, it calculates the last character. This is done by `(n - 1) % 26`. The `-1` is crucial because it maps `1->A, 26->Z` correctly to `0->A, 25->Z`. The rest of the number is then processed by a recursive call with `(n - 1) / 26`. The result of this recursive call is the prefix of our final string, to which we append the character we just calculated. For example, `convertToTitle(28)`: 1. `n=28`. `(28-1)%26 = 1`, which is 'B'. 2. Recursive call with `(28-1)/26 = 1`. 3. `convertToTitle(1)`: `(1-1)%26 = 0`, which is 'A'. 4. Recursive call with `(1-1)/26 = 0`. 5. `convertToTitle(0)` returns `""`. 6. The call for `n=1` returns `"" + 'A'` -> `"A"`. 7. The call for `n=28` returns `"A" + 'B'` -> `"AB"`. ```java class Solution { public String convertToTitle(int columnNumber) { if (columnNumber == 0) { return ""; } // Decrement to map to a 0-25 range columnNumber--; // Recursively find the prefix and append the current character return convertToTitle(columnNumber / 26) + (char)('A' + (columnNumber % 26)); } } ``` ### Algorithm The recursive solution is based on the idea of base conversion. The problem is equivalent to converting a number from base-10 to a special base-26 system where digits are 'A' through 'Z' (representing 1 through 26). 1. **Base Case:** The recursion terminates when the `columnNumber` becomes 0. In this case, an empty string is returned. 2. **Recursive Step:** For any `columnNumber > 0`: a. To handle the 1-based nature of Excel columns (A=1, Z=26) versus the 0-based nature of modulo arithmetic, we first decrement `columnNumber` by 1. This maps the range `[1, 26]` to `[0, 25]`. b. The last character of the Excel title corresponds to `(columnNumber - 1) % 26`. We convert this numeric value (0-25) to its character representation ('A'-'Z'). c. The preceding part of the title is found by recursively calling the function with the quotient `(columnNumber - 1) / 26`. d. The final result is constructed by concatenating the result of the recursive call (the prefix) with the character found in step 2b. ## Iterative Approach This is an iterative version of the base-26 conversion logic. It's generally more efficient than recursion as it avoids the overhead of function calls and eliminates the risk of stack overflow. The core logic remains the same: repeatedly use the modulo operator to find the rightmost digit (character) and division to process the rest of the number. Since we generate characters from right to left (least significant to most significant), we build the string in reverse and then perform a single reversal at the end. **Time:** O(log_{26}(N)) · **Space:** O(log_{26}(N)) **Pros:** Highly efficient in both time and space.; Avoids recursion, making it robust and preventing any chance of stack overflow.; Considered the standard and optimal solution for this type of problem. **Cons:** Requires an explicit reversal step after the loop, which adds a small amount of complexity.; The code might be slightly more verbose than the recursive one. ### Explanation We use a `StringBuilder` for efficient string construction. The loop continues as long as there's a part of the number left to process. In each step, we perform the `(n-1)` trick to align with a 0-indexed system. The remainder of a division by 26 gives us the current character, which we append to our builder. The quotient becomes the new number for the next iteration. This process effectively extracts the base-26 digits from right to left. For example, `columnNumber = 701`: - **Initial:** `sb = ""`, `n = 701` - **Iteration 1:** `n--` -> `n=700`. `rem = 700 % 26 = 24`. `char = 'Y'`. `sb = "Y"`. `n = 700 / 26 = 26`. - **Iteration 2:** `n--` -> `n=25`. `rem = 25 % 26 = 25`. `char = 'Z'`. `sb = "YZ"`. `n = 25 / 26 = 0`. - **End Loop:** `n` is now 0. - **Final Step:** `sb.reverse()` gives `"ZY"`. Return this string. ```java class Solution { public String convertToTitle(int columnNumber) { StringBuilder result = new StringBuilder(); while (columnNumber > 0) { // Decrement to map to a 0-25 range columnNumber--; // Get the remainder and convert to character int remainder = columnNumber % 26; result.append((char) ('A' + remainder)); // Update columnNumber for the next digit columnNumber = columnNumber / 26; } // The result is built in reverse, so reverse it before returning return result.reverse().toString(); } } ``` ### Algorithm This approach uses a loop to perform the base conversion iteratively, which avoids the overhead of recursion. 1. Initialize an empty `StringBuilder` to construct the result string. 2. Start a `while` loop that continues as long as `columnNumber` is greater than 0. 3. Inside the loop: a. Decrement `columnNumber` by 1 to map the 1-26 range to a 0-25 range. b. Calculate the remainder: `rem = columnNumber % 26`. This gives the 0-indexed value of the current character. c. Convert the remainder to its corresponding character `(char)('A' + rem)` and append it to the `StringBuilder`. d. Update `columnNumber` for the next iteration by integer division: `columnNumber = columnNumber / 26`. 4. After the loop finishes, the `StringBuilder` will hold the characters of the title in reverse order. 5. Reverse the `StringBuilder` and convert it to a `String` to get the final correct title. # Solutions ### CSharp ```csharp public class Solution { public string ConvertToTitle(int columnNumber) { StringBuilder res = new StringBuilder(); while (columnNumber != 0) { --columnNumber; res.Append((char)('A' + columnNumber % 26)); columnNumber /= 26; } return new string(res.ToString().Reverse().ToArray()); } } ``` ### Java ```java class Solution { public String convertToTitle(int columnNumber) { StringBuilder res = new StringBuilder(); while (columnNumber != 0) { --columnNumber; res.append((char)('A' + columnNumber % 26)); columnNumber /= 26; } return res.reverse().toString(); } } ``` ### Python ```python class Solution: def convertToTitle(self, columnNumber: int) -> str: res = [] while columnNumber: columnNumber -= 1 res . append(chr(ord('A') + columnNumber % 26)) columnNumber //= 26 return '' . join(res[:: - 1]) ```