Excel Sheet Column Title

excerpt: This covers the building blocks such as Modulo Operator, Reducing the Input Value and Integer Division. tags: modulo-operator reducing-input-value integer-division

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"

Example 4:

Input: columnNumber = 2147483647
Output: "FXSHRXW"

Constraints

  • 1 <= columnNumber <= 231 - 1

Solution

Create an array of capital letters from A to Z. Repeat till the given number is not reduced to 0, calculate the first alphabet and reduce the input by using integer division. We need to subtract one because 0-index based array is used.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

# @param {Integer} column_number
# @return {String}
def convert_to_title(n)
  a = ('A'..'Z').to_a
  s = ''

  while n != 0 do
    s = a[n % 26 - 1] + s
    n = (n-1) / 26
  end
  
  s
end

The key insight to solve this problem is modulo operator can be used to cycle through a set of values. In this case, A to Z. The wraparound behavior of modulo operator comes in handy in solving some problems.

Building Blocks

  • Modulo Operator
  • Reducing the Input Value
  • Integer Division

You can convert a given integer to its corresponding Excel column title by repeatedly dividing the number by 26 and using the remainder to find the corresponding letter in the alphabet. The steps are as follows:

  1. Initialize the Result: Start with an empty string to build the result.

  2. Loop Until Zero: Repeat the process until the column number becomes zero.

    a. Calculate Remainder: Subtract one from the column number and take the remainder when dividing by 26.

    b. Find Character: Convert the remainder to a character by adding it to the ASCII value of ‘A’.

    c. Add to Result: Add the calculated character to the beginning of the result string.

    d. Update Column Number: Divide the column number by 26 after subtracting one.

  3. Return the Result: The final result string will contain the corresponding column title.

Here’s the code:

1
2
3
4
5
6
7
8
9

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

This code runs in O(log n) time, where n is the input column number, and it uses O(1) extra space. It builds the result string from right to left, efficiently calculating the corresponding characters for each position.

“Excel Sheet Column Title” involves converting a given integer to a corresponding column title as it would appear in an Excel sheet. It requires the understanding of numbers’ representation in different bases (particularly base-26 in this case).

10 Prerequisite LeetCode Problems

This problem can be one of the first problems when learning about number system conversions. Here are some problems to solve before tackling this problem:

  1. Reverse Integer (LeetCode 7): Understanding how to handle digits of a number.
  2. Add Binary (LeetCode 67): Basic string manipulation and understanding of binary numbers.
  3. Add Digits (LeetCode 258): More practice on dealing with digits of a number.
  4. Number of 1 Bits (LeetCode 191): Understanding bit manipulation and binary numbers.
  5. Power of Two (LeetCode 231): Understanding properties of numbers in binary.
  6. Counting Bits (LeetCode 338): Bit manipulation and dynamic programming.
  7. Power of Four (LeetCode 342): More advanced properties of binary numbers.
  8. Single Number (LeetCode 136): Understanding bitwise XOR operation.
  9. Binary Watch (LeetCode 401): Converting integers to binary and understanding their representation.
  10. Complement of Base 10 Integer (LeetCode 1009): Flipping bits and understanding binary to decimal conversion.

These cover manipulating numbers and their representations, which are useful in solving the “Excel Sheet Column Title” problem.

Problem Classification

This problem can be classified as a “Number System Conversion” problem in the “Mathematics” domain. It’s about converting a decimal number into a specific base-26 number system (where 1 corresponds to ‘A’, 2 to ‘B’, …, 26 to ‘Z’), similar to how hexadecimal conversion works in base-16. Here, however, we’re not just changing to base-26, but also mapping each digit to a specific letter, which adds a string manipulation aspect to the problem.

Language Agnostic Coding Drills

This problem involves mapping an integer into an equivalent title, based on the conventions of spreadsheet software (e.g., ‘A’ for 1, ‘Z’ for 26, ‘AA’ for 27, and so on). Here’s how we could break down this problem into incremental steps or ‘drills’:

  1. Understanding Basic String Manipulation: Familiarize yourself with how to manipulate strings in your language of choice. This includes learning how to concatenate strings and add characters to strings.

  2. Understanding Modulo Operation: The modulo operation returns the remainder of a division operation. In this problem, it’s used to map numbers to their corresponding alphabetical letters.

  3. Understanding Integer Division: Integer division (or floor division) returns the largest whole number that’s less than or equal to the exact quotient. In this problem, it’s used to decrement the number until it reaches zero, which signals the end of the conversion.

  4. Understanding Loops and Control Flow: This problem involves a loop that continues until a condition is met (in this case, until the number becomes zero). Understanding how to set up and control such loops is essential.

The approach to solving this problem could be as follows:

  • Start with the given number.
  • Use a loop to repeatedly perform operations until the number becomes zero.
  • Inside the loop, subtract one from the number (to account for the fact that ‘A’ maps to 1 and not 0), and then calculate the remainder when the number is divided by 26.
  • Use this remainder to index into the string of alphabet letters, and prepend this letter to the start of the answer string.
  • Update the number by performing integer division by 26.
  • After the loop ends, return the answer string, which will contain the title corresponding to the original number.

Targeted Drills in Python

  1. Understanding Basic String Manipulation:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# concatenating strings
str1 = "Hello"
str2 = "World"
result = str1 + " " + str2
print(result) # Output: "Hello World"

# adding character to string
char = '!'
result += char
print(result) # Output: "Hello World!"
  1. Understanding Modulo Operation:
1
2
3
4

# calculate remainder of division
num = 27
remainder = num % 26
print(remainder) # Output: 1
  1. Understanding Integer Division:
1
2
3
4

# calculate quotient of division
num = 27
quotient = num // 26
print(quotient) # Output: 1
  1. Understanding Loops and Control Flow:
1
2
3
4
5

# print numbers 1 to 10 using a while loop
num = 1
while num <= 10:
    print(num)
    num += 1

Here’s the final solution combined all of the concepts together:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def convertToTitle(n: int) -> str:
    abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    ans = ""
    while n:
        n -= 1
        ans = abc[n % 26] + ans
        n = n // 26
    return ans

print(convertToTitle(27)) # Output: "AA"

This code starts a loop with the given number, n, and continues until n becomes zero. In each iteration, it calculates the current character using the modulo operator, then prepends it to ans. Finally, it updates n by doing integer division by 26. When n becomes zero, the loop ends, and the function returns ans as the result.