Last Updated: 19 Dec, 2020
Excel Equivalent of a Decimal Number
Moderate
Asked in companies
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.
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
Approaches
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:
- 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.
- 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”.
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’.
The idea is to use an approach similar to finding the binary representation of a decimal number. In the binary representation, we have only 2 numbers i.e 0 or 1. but here we have 26 characters from “A” to “Z”. So, we will find an Excel Equivalent using the Base 26 Conversion.
The two primary difference here being :
- 0 remainder corresponds to “A”, 1 remainder corresponds to “B”, 2 remainder corresponds to “C”……, 25 remainder corresponds to “Z”.
- To accommodate the absence of 0 in our number system we will use ‘N’ - 1 in place of ‘N’ at the start of each iteration of the while loop.
The Steps are as follows:
- Initially, we create an ‘ANSWER’ string.
- Then run a loop until ‘N’ > 0 and do:
- ‘N’ = ‘N’ - 1(For dealing with 0).
- Add the ('A' + ‘N’ % 26) to the answer array.
- ‘N’ = ‘N’ / 26.
- At last reverse the ‘ANSWER’ which will be the Excel Equivalent of the number 'N'.
For Example: If the given number ‘N’ = 750.
We first subtract 1 from 750 i.e now ‘N’=749, then we find the remainder of N with 26 i.e 21 so as we consider the 0 remainder corresponds to “A”, 1 remainder corresponds to “B”,.... and 21 remainder corresponds to “V”, so we add “V” to our answer, then we divide ‘N’ with 26.
Now ‘N’ will become 28, then again we subtract 1 from ‘N’ and find the remainder with 26 i.e 27 % 26 is 1. So “B” corresponds to 1, therefore we add B to ‘ANSWER’, then we again divide ‘N’ with 26.
Now ‘N’ will become 1, then again subtract 1 from ‘N’ .ie remainder of 0 with 26 is 0 So ”A” corresponds to 0, therefore we add “A” to the answer.
Now our answer is having “VBA”. which is the reversed of our answer so reversed the ‘ANSWER’ i.e “ABV” which is the Excel Equivalent of the number 750.