Saturday 22 November 2014

Excel Sheet Row Numbers

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.

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 % 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.

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

No comments:

Post a Comment