# Jingshao

## A Simple Interview Question I ran into an interview question on leetcode about a number conversion that marked as easy. It reveals the beauty of our numbering notation.

## Question

``````Excel Sheet Column Title

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

For example:
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
...

Example 1:
Input: 1
Output: "A"

Example 2:
Input: 28
Output: "AB"

Example 3:
Input: 701
Output: "ZY"
``````

## Solution (Incorrect)

At first glance, I thought it is just a simple conversion to a base 26 number. The obvious solution is:

``````string convert(int n) {
string s = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string result = "";
int r;
while(n) {
r = (n - 1) % 26;
n /= 26;
result = s[r] + ret;
}
return result;
}
``````

However, it is incorrect. When `n` is `27`, instead of `AA`, it returns `BA`. Hmm, that is because `27-1` is `26`, which in 26 bassed numbering system carries one digit to the higher position and becomes `10`. In our wrong notation system, where `B` is equivalent to `1`, and `A` is equivalent to `0`, `10` is noted as `BA`.

## Analysis

If we observe the question more closedly, we can find there is something special to the notation. It does not have a notation for `0`! It is like in decimal, if we count 1, 2, 3, …, 9, then the next one, instead of 10, we couldn’t write it down, because there is no `0`! Hmm, this question must be created by an ancient mathmetician before the Indian invented `0`.

So how can we fix it?

Let’s study the current decimal system that has `0`. In decimal, a number 234 is actually `2 x 100 + 3 x 10 + 4 x 1`. A number 240 is `2 x 100 + 4 x 10 + 0 x 1`. A number 108 is `1 x 100 + 0 x 10 + 8 x 1`. The position in the number corresponding to how many powers of 10, and the number is the coefficient. So `942` the number `9` at the position (from left to right, start with 0) `2`, means you need to times number `9` with `10` to the powers of `2` (`100`), and the number `4` at the position `1`, means you need to times number `4` with `10` to the powers of `1` (`10`), and the number `2` at the position `0`, means you need to times number `2` with `10` to the powers of `0` (`1`).

``````
position       2        1       0
|        |       |
v        v       v
number         9        4       2
^        ^       ^
|        |       |
Power of 10    2        1       0
Value       9 x 100 + 4 x 10 + 2 x 1 = 942
``````

If we omit `0`, then we cannot tell the difference between 108 and 18, or 10008! You see how important `0` is in our numbering system?

What to do if there is no `0`?

Let’s look at the number little more closely to figure out if there is a solution for this. A number `240` means `2 x 100 + 4 x 10 + 0 * 1`, if there is no `0`, we can do this: `240 = 23 = 2 x 100 + 3 x 10 + 10`. Here I use `` as a notation means `10` occupies the last position. There, no zero is needed! Let’s use a single symbol to replace the ``, say, `A`, then `23` can be written as `23A`. and `108` can be written as `A8`.

From 1 to 110 becomes:

`````` 1,  2,  3,  4,  5,  6,  7,  8,  9,  A,
11, 12, 13, 14, 15, 16, 17, 18, 19, 1A,
21, 22, 23, 24, 25, 26, 27, 28, 29, 2A
...
91, 92, 93, 94, 95, 96, 97, 98, 99, 9A
A1, A2, A3, A4, A5, A6, A7, A8, A9, AA
``````

This, is exactly what we need! All we need to do is when a position should be `0`, we borrow a `10` from the higher position and use our `A` to note a `10`.

## Solution

Now back to the original question, the solution become obvious. When the remainder is `0`, instead of use `0`, we borrow `26` from the higher position, and write an `Z` instead of `0`.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 `````` ``````string p(int n) { string s = "0ABCDEFGHIJKLMNOPQRSTUVWXYZ"; string ret = ""; while(n) { int r = n % 26; if (r == 0) { // borrow 26 from the higher position r = 26; n -= 26; } n /= 26; ret = s[r] + ret; } return ret; } ``````