Microsoft Excel Sheet Question-very Important

Given the sequence S1 = {a,b,c,d,…,x,y,z,aa,ab,ac…. } and given that this sequence corresponds (term for term) to the sequence S2 = {0,1,2,3,….}. Write code to convert an element of S2 to the corresponding element of S1.

Hint:

I’ve created the following table for your convenience.

a - 0 aa - 26 ..... za - 676 aaa - 702
b - 1 ab - 27 ..... zb - 677 aab - 703
c - 2 . . .
. . . .
. . . .
. . . .
z - 25 az - 51 ..... zz - 701 aaz - 727

From a-z, how many of them are there? How about aa-zz? And aaa-zzz?
Amazon’s HQ in Seattle

Solution:
You should be able to observe that from a-z (a total of 26), from aa-zz (a total of 262), from aaa-zzz (a total of 263), and so on… I will explain why this is important later.

Assume s1 = abc and we need to find its corresponding number, s2. Now imagine that aaa can be magically transformed to 000, aab –> 001, …, and abc to some number xyz. The question is, what should xyz be?

Now this is a trivial question. Why? Remember that our numeral system has 10 as its base. Here, we are merely converting the system from base 26 to base 10. Therefore, xyz = 2*260 + 1*261 + 0*262 = 28.

But wait, we are not finished yet. To find the real value of s2, we need to find how many of them appeared before aaa and add to xyz. Using the important observation earlier, we can easily determine that that there are a total of 26 + 262 = 702 that appeared before aaa. Therefore, s1 corresponds to the number s2 = 28 + 702 = 730.

Assume that we are converting from s2 = n to s1 = “abcde…”.
We can generalize to the following equation (Equation (1)):

Equation (1)

n = 26 + 262 + ... + 26k-1 + a0 + a1*26 + a2*262 + ... + ak-1*26k-1
= a0 + (a1 + 1) 26 + (a2 + 1) 262 + ... + (ak-1 + 1) 26k-1

where
ai ranges from 0-25 (each representing a letter in s1),
k is the number of letters in s1.

To solve the above equation, we have to find the values of a0, a1, …, ak-1. Once we solve this equation, we are able to determine the string of letters of s1 directly.

a0 can be solved by taking n % 26. Why? Because a0 ranges from 0-25, which is not divisible by 26, while the rest are factor of 26. After we obtained the value of a0, we divide n by 26. This will yield the number

n' = (a1 + 1) + (a2 + 1) 26 + ... + (ak-1 + 1) 26k-2

You might think that a1 + 1 = n’ % 26. This is wrong. What happens when a1 = 25? For sure, a1 +1 is divisible by 26, and thus the mentioned equation is invalid. We can easily resolve this by doing a1 = (n’ – 1) % 26.

The rest is easy, we continue further with n” = (n’ – 1) / 26 and a2 = (n” – 1) % 26, up until ak-1.

Clearly, we need to do both modulo 26 and divide by 26 operations a total of k-1 times. But do we really need to know the value of k (or the number of letters in s1)?

The beauty of this method is, since we start from the least significant digit and work our way up, we don’t need to evaluate k. We just need to divide n by 26 repeatedly until it becomes 0.

so then we can write

#include
#include
/* Convert the header to a number */
int main()
{
char header[] = "abc";
char temp;
int number = 0;
int len, i;
len = strlen(header);
printf("len : %d\n", len);
for(i = 0;i < len; i++)
{
number += (int)pow (26, (double)i) * (header[i] - 'a' + 1);

}
printf("number : %d\n", number);
/* Convert back the number to string header */
while(number != 0)
{
temp = number%26;
number = number/26;
printf("%d %c\t", temp ,temp + 'a'-1);
}
return 0;
}

Time Complexity O(N*26^N) for string to Number
Space Complexity O(K) Where K Number of digits in Number =O(1) Constant
Run here http://codepad.org/DNBbGm7j