Given the sequence

Refer: http://leetcode.com/2010/10/amazon-bar-raiser-interview-question.html

**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**.Equation(1)n= 26 + 26^{2}+ ... + 26^{k-1}+a_{0}+a_{1}*26 +a_{2}*26^{2}+ ... +a_{k-1}*26^{k-1}=a_{0}+ (a_{1}+ 1) 26 + (a_{2}+ 1) 26^{2}+ ... + (a_{k-1}+ 1) 26^{k-1}wherea_{i}ranges from 0-25 (each representing a letter ins_{1}),kis the number of letters ins_{1}.

To solve the above equation, we have to find the values of

*a*_{0}*, a*_{1}*, …, a*_{k-1}. Once we solve this equation, we are able to determine the string of letters of**directly.***s*_{1}*a*

_{0}can be solved by taking

*n*% 26. Why? Because

*a*

_{0}ranges from 0-25, which is not divisible by 26, while the rest are factor of 26. After we obtained the value of

*a*

_{0}, we divide

*n*by 26. This will yield the number

*n'* = (*a*_{1} + 1) + (*a*_{2} + 1) 26 + ... + (*a*_{k-1} + 1) 26^{k-2}

You might think that

*a*_{1}+ 1 =*n’*% 26. This is wrong. What happens when*a*_{1}= 25? For sure,*a*_{1}+1 is divisible by 26, and thus the mentioned equation is invalid. We can easily resolve this by doing*a*_{1}= (*n’*– 1) % 26.
The rest is easy, we continue further with

*n”*= (*n’*– 1) / 26 and*a*_{2}= (*n”*– 1) % 26, up until*a*_{k-1}.
## No comments:

## Post a Comment