Excel Equivalent of a Decimal Number

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in companies
AdobeMAQ Software

Problem statement

Given a positive number 'N'. Your task is to find the Excel Equivalent of the number 'N'.

Note:

1. The Excel equivalent of 1 is "A", the Excel equivalent of 2 is "B" ……………, the Excel equivalent of 26 is "Z". 

2. The Excel equivalent of 27,28…,52 is "AA", "AB"…."AZ" respectively.

3. The Excel Equivalent of 53,54….78 is "BA", "BB"….."BZ".

4. The pattern shown above can be used to find the excel equivalent of any positive number.

5. There is only one Excel Equivalent for a given positive number.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ denoting the number of test cases.

The first and only line of each test case contains a number 'N' of which the Excel Equivalent is required to be found.
Output format: 
For each test case, return the Excel equivalent of a given number in a separate line.
Note: 
You don't need to print anything, it has already been taken care of. Just implement the given function.
Follow Up: 
Can you solve this in logarithmic time and space complexity?
Constraints: 
1 <= T <= 1000
1 <= N <= 10^15

Time limit: 1sec
Sample Input 1:
2
2
9
Sample Output 1:
B
I
Explanation of Sample Output 1:
In test case 1, the Excel Equivalent of 2 is B.

In test case 2, the Excel Equivalent of 9 is I.
Sample Input 2:
2 
27
31
Sample Output 2:
AA
AE
Explanation of Sample Output 2:
In test case 1, the Excel equivalent of 26 is Z and therefore the Excel equivalent of 27 is AA.

In test case 2, the Excel equivalent of 27 is AA and therefore the Excel equivalent of 31 will be AE.
Hint

Try to think of finding out Excel equivalent of ‘N’ from Excel equivalent of ‘N’ - 1

Approaches (2)
Brute Force approach

The idea is to generate all the Excel equivalents from 1 to ‘N’. The process of generating Excel equivalent of ‘N' from ‘N’ - 1 can be divided into two cases:

 

  1. The last character of Excel Equivalent of ‘N’ - 1 is not equal to “Z”, In this case, we can find the Excel equivalent of ‘N’ by incrementing the last character of ‘N’ - 1 by 1 and keeping the rest of the characters unchanged. For eg: “AA”->"AB" , “BCD”->"BCE" etc.
  2. The last character of Excel equivalent of 'N' - 1 is equal to “Z”, In this case, we have to find the first character from the right which is not equal to “Z” and increment it by 1 and set all the other characters on the right to “A”. If there is no such character in the string we will add an extra “A” to the string and set all the other characters also to “A”.
  3.  

Using the following approach we can generate the Excel Equivalent of 1,2… 'N' and then finally we will output the Excel Equivalent of ‘N’.

Time Complexity

O(N * log26(N)), Where ‘N’ is the number which the Excel Equivalent is required to be found.

 

Since we will generate Excel Equivalent of all the values from 1 to N and the logarithmic factor is because the length of the Excel Equivalent for a number N is log26(N). So the overall time complexity is O(N * log26(N)).

Space Complexity

O(log26(N)), Where ‘N’ is the number of which the Excel Equivalent is required to be found.

 

Since to generate the Excel Equivalent of N we need to store only the Excel Equivalent of N - 1 and space will only be the space required to store Excel equivalent of a single number which is in worst case is log26(N). Hence the overall space complexity will be O(log26(N)).

Code Solution
(100% EXP penalty)
Excel Equivalent of a Decimal Number
Full screen
Console