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[10] = 2 x 100 + 3 x 10 + 10. Here I use [10] as a notation means 10 occupies the last position. There, no zero is needed! Let’s use a single symbol to replace the [10], say, A, then 23[10] 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

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;
}