Excel Header Problem
PROBLEM
Given a number, n, return the heading of the nth-column in Excel.
Feel free to give this challenge a try before reading further.
SOLUTION
Step 1:
The first step is easy enough: return the letter that corresponds with the numbers 1–26. Here’s how I did it:
letters = 'abcdefghijklmnopqrstuvwxyz'.upper()Using the letters variable, I can access the letters like so:
letters[0]
>>'A'
letters[25]
>>'Z'To ensure the number n corresponds with the proper indexing, subtract 1:
#--should return 'A'
n = 1
letters[n-1]
>>'A'When n becomes larger than 26, a new letter is added to the beginning like so:
letters[27]
>>'AA'
letters[28]
>>'AB'
This is where I got stuck when I first attempted the problem.
How do I create a variable that can dynamically change its length?
Step 2:
Create a variable that can store the final result.
result = ""Also create the following variables:
num = 1
lower_bound = 26**(num-1)
upper_bound = 26**(num)- The num variable stores how long the result string will be
- The lower_bound will store the lower bound for a solution of length num
- The upper_bound will store the upper bound for a solution of length num
With these initial values set, loop until n is within our bounds.
while n > upper_bound:
num += 1
lower_bound += 26**(num-1)
upper_bound += 26**(num)- If n is higher than the original upper_bound variable, I want to increase the number of letters result will be and increase the bounds
- We want to ADD the next power of 26 to each bound
- I want this to keep happening until n is within the lower_bound and upper_bound variables → use a while loop since I don’t know how many times this will need to be done beforehand
We add to the bounds to ensure they are offset by the previous bounds. If we didn’t, our lower_bound and upper_bound variables would be too low.
#--if lower_bound and upper_bound didn't add
num = 2
lower_bound = 26**(num-1)
upper_bound = 26**(num)
print(lower_bound, upper_bound)
>>26, 676
#--should be 27 and 702
Step 3:
Now that the lower and upper bounds are taken care of, we move on to the most difficult part of the problem: determining the correct letter and determining the correct position based on n.
Let’s test it out with the value 105. I opened Excel to verify the answer and found it to be ‘DA’.
#27-52 --> 'A_'
#53–78 --> 'B_'
#79-104 --> 'C_'
#105 --> 'DA'
My first thought was to use modular arithmetic. We can see that no matter what the other letters are, the last letter can be determined this way. We will use this fact later, but for now, let’s see how it works with some examples:
# n = 52
letters[(n % 26)-1]
>>'Z'
# n = 105
letters[(n % 26)-1]
>>'A'
But, the problem is that we want a repeatable process that can be done for each letter, regardless of the position. The modular arithmetic will only work on the final letter.
Let’s think about the 2-letter examples. There are 26 partitions between lower_bound and upper_bound, one for each starting letter. Is there a way to partition this range 26 ways that won’t change for the values between partitions? For instance, going from 27 to 52 should still produce an ‘A’ for the first letter while the second letter changes.
Get Viktor Dominguez’s stories in your inbox
Join Medium for free to get updates from this writer.
The answer: floor division.
Floor division allows you to divide a number and then round down, essentially only returning the integer value. It’s similar to modular division in that each one drops the remainder, but floor division will keep the same value over large ranges. Here’s an example:
# n = 105
# floor div
n // 26
>>4
# mod div
n % 26
>>1
# n = 110
# floor div
n // 26
>>4
# mod div
n % 26
>>6We know the length of our answer, the bounds for the integer n, and what methods we can use. Now, we just need a repeatable method and apply it to find the letter at each position.
Step 4:
We know that floor division will allow us to find letters over ranges. We also know that we will be splitting each range into 26 partitions doing this. But, we need a way to do this for large numbers so that it doesn’t return a number outside of our index range (0–25).
# n = 660
n // 26
>> 26
# n = 703
n // 26
>> 27If we think about each position, we can use floor division based on the corresponding powers of 26. For 2-letter solutions, we will want to use 26**1 and 26**0 for the first and second positions respectively. For 3-letter solutions, we will add an additional divisor of 26**2 to the beginning.
Let’s go back to our target of n = 105, which corresponds to ‘DA’, and see if we can spot some patterns when we apply this division.
# n = 105
n // 26 # Higher power = Earlier position
>>4
n // 1 # Lower power = Later position
>>105We can see that 4 % 26 will return 4 and 105 % 26 will return 1. We are looking for 3 and 0 respectively so that we can index letters and return ‘D’ and ‘A’. Looks like all we need to do is subtract 1 and do modular division.
But, let’s see what happens when we try this.
# n = 105
(n-1) // 26 % 26
>>4
(n-1) // 1 % 26
>>0It worked for the final position, but not the first. That’s because (n-1) is 104, and 104 // 26 is still 4.
It seems that the (n-1) trick did not work as intended. The last letter is correct because anything divided by 1 will be itself. This essentially becomes a modular division problem, which we stated earlier would be the way to solve the last letter. Now, we must turn our focus to the first letter.
We know that we want some value that will return a 3 when the modular division is applied to it. This could be a 3, a 29, a 55, etc. This is when I realized how to get the solution.
The numbers 27–52 are reserved for the letter ‘A’ columns. The numbers 53–78 are reserved for the letter ‘B’ columns. This pattern continues for each set of 26 numbers until we reach the final partition of 677–702, which is reserved for the letter ‘Z’ columns.
Our floor division didn’t work before because we did not account for the offset AKA the lower_bound variable. If we subtract this out, we will get the desired ranges. Now, the ranges become the ones that we are familiar with:
- 0–25 for ‘A’
- 26–51 for ‘B’
- 52–77 for ‘C’
- etc.
When applying floor division to 0–25, this will return a 0. When applying the same floor division to 26–51, this will return a 1. This can then be used for the indexing of letters directly without subtracting any other values.
# n = 105
letters[(n-lower_bound)//1%26]
>>’A'
letters[(n-lower_bound)//26%26]
>>’D'The last thing to do was to test it with a higher value of n.
We can use 703, which is the first 3-letter value. Let’s see what happens for this number:
# n = 703
letters[(n-lower_bound) // (26**2) % 26]
>>'A'
letters[(n-lower_bound) // (26**1) % 26]
>>'A'
letters[(n-lower_bound) // (26**0) % 26]
>>'A'Perfect, we have found our solution! For n = 703, (n-lower_bound) will equal 0 so all of the divisions return 0. If we increased the number by 26, we will get n = 729 and (n-lower_bound) will equal 26. This number should result in a ‘ABA’ pattern. Here is how the floor divisions break down for this value:
26 // 1
>>26 #26 % 26 = 0 --> 'A' last letter
26 // 26
>> 1 #1 % 26 = 1 --> 'B' middle letter
26 // 26**2
>>0 #0 % 26 = 1 --> 'A' first letterAll that is left is finding a way to do this the desired number of times and returning the output.
for i in range(num):
result += letters[(n-lower_bound) // (26**i) % 26]
print(result[::-1])The final line reverses the order of result so that it is in the correct order. We can skip this if we rewrite the for loop as so:
for i in range(num-1,-1,-1):
result += letters[(n-lower_bound) // (26**i) % 26]
print(result)Final Solution
n = int(input("Please enter in an integer greater than 0: "))
letters = 'abcdefghijklmnopqrstuvwxyz'.upper()
result = ""
num = 1
lower_bound = 26**(num-1)
upper_bound = 26**num
while n > upper_bound:
num += 1
lower_bound += 26**(num-1)
upper_bound += 26**num
for i in range(num):
result += letters[(n-lower_bound)//(26**i)%26]
print(result[::-1])
