This is a problem on LeetCode and it's classified as "easy." I've been at this for hours, even called in a colleague. I can't figure out the fault in my logic. I'm not looking for a completely different solution to the problem. I'd just be grateful if someone could point out what's wrong with my approach.
The idea is to convert an int to a string that is represented as an Excel column header (1='A', 2='B' ... 27='AA', etc.). Here is my code, with comments. The code works for many inputs (e.g., 735 -> 'ABG'), but fails on others (e.g., 702 -> 'ZZ').
def numToCol(n):
# Generate a key such that {1:'A', 2:'B', 3:'C'... 26:'Z'} (this works fine)
key = {}
for i in range(65, 91):
key[i-64] = chr(i)
# According to Wikipedia, the number of digits in the bijective base-k
# numeral representing a nonnegative integer n is floor(logk((n+1)*(k-1)))
# exp = num of letters in final string
exp = int(math.log((n+1)*25, 26)) # int() rounds it down
col_name = ''
num = n
# The final number is represented by a(26**0) + b(26**1) + c(26**2) + ...
# If exp = 3, then there are 3 letters in the final string, so we need to find
# a(26**2) + b(26**1) + c(26**0).
# If exp = 3, i iterates over 2, 1, 0.
for i in range(exp-1, -1, -1):
# factor = how many 26**i's there are in num, rounded down
factor = int(num/(26**i))
# add to the string the letter associated with that factor
col_name = col_name + key[factor]
# update the number for next iteration
num = num - (factor*(26**i))
return col_name
Here is a function I wrote to go the reverse direction (convert string to int). This helps to see what the expected result should be. It's confirmed to work.
def colToNum(string):
'''
Converts an upper-case string (e.g., 'ABC') to numbers as if they were
column headers in Excel.
'''
key = {}
for i in range(65, 91):
key[chr(i)] = i-64
new = []
for idx, val in enumerate(string[::-1]):
new.append(key[val] * 26**idx)
return sum(new)
Was able to find the fault, but didn't find an elegant way of solving the problem. As you might have noticed, the code always fails whenever you get to Z and there is more than one letter. That's because the factors that should be, for example, 2 and 26, meaning BZ, become 3 and 0. And this zero leads to the problem. Here is the hack that manages to make the code work. Everything is the same except for the if-statement (and num = num - (factor*(26**i)) has been moved up)
for i in range(exp-1, -1, -1):
# factor = how many 26**i's there are in num, rounded down
factor = int(num/(26**i))
num = num - (factor*(26**i))
if num == 0 and i!=0:
factor -=1
num = 26
# add to the string the letter associated with that factor
col_name = col_name + key[factor]
This if-statements just fixes these "Z" cases that happen whenever there is more than one letter in the result.