Excel Sheet Column

2018-03-17

In this tutorial, we will introduce how to solve the conversion between excel sheet column name and decimal numbers problems. Leetcode [#168. Excel Sheet Column Title and #171. Excel Sheet Column Number]. These problems are easy to solve, but for such a long time, I can’t totally understand why it should be solved like the discussion page said, which makes me crazy and confused. Finally, I realized that they are actually games between different numeral systems. In the following, we will analysis the two problems in detail.

Problem Description

#171. Given a column title, return its corresponding positive integer.

#168. Given a positive integer, return its corresponding column title as appear in an Excel sheet.

1
2
3
4
5
6
7
8
9
1 <-> A
2 <-> B
3 <-> C
...
26 <-> Z
27 <-> AA
28 <-> AB
...
702 <-> ZZ

Analysis of #171.

#171 is easier than #168 because you can easily find the rules through several examples. We only need to multiply each digit’s number and its corresponding significance value and sum them up.

1
2
3
AC = A * 26 + C = 1 * 26 + 3 = 29
BCZ = B * 26^2 + C * 26 + Z = 2 * 26^2 + 3 * 26 + 26 * 1
NBAD = N * 26^3 + B * 26^2 + A * 26 + D * 1 = 14 * 26^3 + 2 * 26^2 + 1 * 26 + 4 * 1 = 247446

1
2
3
4
5
6
7
def n1_to_n3(s):
    """Convert N1 to N3."""
    n, base = 0, 1
    for ch in s[::-1]:
        n += (ord(ch) - ord("A") + 1) * base
        base *= 26
    return n

Analysis of #168.

We can assume that this is a new kind of numeral system N1. Listing some examples, we can find that there are 2 differences between it and our familiar decimal system.

1
2
3
N1
1. In this new system, there is no 0, which starts from 1.
2. Its base is 26. (A~Z)

For simplicity, let’s see another similar numeral system N2, which is defined like this:

1
2
3
4
N2
1. There is no 0, which starts from 1.
2. Its base is 10. (1~9, we represent 10 as 'x')
3. In decimal system, when one digit reaches 10, a carry digit will be added in front of it. Whereas in this system, when one digit reaches larger than 10, a carry digit will be added.

So the numbers in system N2 look likes this:

1
2
3
4
5
N2
 1,  2,  3,  4,  5,  6,  7,  8,  9,  x,
11, 12, 13, 14, 15, 16, 17, 18, 19, 1x,
21, 22, 23, 24, 25, 26, 27, 28, 29, 2x,
...

And the numbers in normal decimal system N3 look like this:

1
2
3
4
5
N3
0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10,
   11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
   21, 22, 23, 24, 25, 26, 27, 28, 29, 30,
   ...

Compare N2 with N3, we can find out that, the only difference is in the last column, other columns are the same. And in the N2’s last column, ‘x’ represents ‘10’, ‘1x’ represents ‘1*10 + 10’, ‘2x’ represents ‘2*10 + 10’. The rule of converting N3’s ‘30’ to N2’s ‘2x’ is:

1
2
3
base = 10
1. we minus a 10 from 30, and represent [bit2] as 'x' .
2. the left part is 20, and [bit1] is 20 // base.

For other numbers which is not multiple of 10, their representations are same in N2 and N3. So we can convert N3 to N2 using the following algorithm:

1
2
3
4
5
6
7
8
9
10
11
12
def n3_to_n2(n):
    """Convert N2's number to N3's number."""
    s = ""
    base = 10
    while n > 0:
        if n % base == 0:  # multiple of 10
            s += "x"
            n -= base
        else: # not multiple of 10
            s += chr(n % base - 1 + ord("1"))
        n //= base
    return s[::-1]

We know that N1 has the similar rule with N2, the only difference is that N1 uses base 26, wheras N2 uses base 10. So we can convert N3 to N1 using similar idea.

1
2
3
4
5
6
7
8
9
10
11
12
def n3_to_n2(n):
    """Convert N2's number to N3's number."""
    s = ""
    base = 26
    while n > 0:
        if n % base == 0:  # multiple of 26
            s += "Z"
            n -= base
        else: # not multiple of 26
            s += chr(n % base - 1 + ord("A"))
        n //= base
    return s[::-1]