Excel Column Title | InterviewBit | Solution Explained
Excel Column Title is a math problem on InterviewBit. I explain the solution using a simple approach. Problem Link.
This solution is the inverse of: Excel Column Number | InterviewBit | Solution Explained
0. Excel Column Title: Problem Discussion
0.0. IO Format
- input:
- an integer
- output:
- a string of characters, which is the equivalent of the input integer
- constraints:
- characters output capital English letters
- solution must be better than O(N) time and space each
0.1. Examples
The problem statement is weird, so let’s take a look at some examples.
- 1 -> A
- 2 -> B
- 26 -> Z
- 27 -> AA
- 52 -> AZ
And so on.
1. Excel Column Title: Observations & Logic
1.0. Intuitions
It is clear that we map integers from 1 to 26 to A to Z respectively and then from 27, we add one more A, at the string position 1 with A at position 0, to create 27. That is, 27 = 261 * val(A) + 260 * val(A).
1.1. Building Upon the Intuitions
We notice that to extract out the characters from the integer, we need to be able to break it into powers of 26. But that already sounds a bit cumbersome, yeah?
So let’s make life easy. First, instead of bothering with the appropriate power of 26, let’s extract the remainder of 26. Then, we will set the number to be number/26.
1.2. Example Explanation
Confused? Let’s take the case of 352569. First, we get the remainder with 26 = 9. This means that the letter is “I” (capital i). Then we divide 352569 by 26 = 13560.
Now, we do the same.
- Extract the remainder: 13560%26 = 14
- Map the remainder: N
- Divide the number: 13560/26 = 521
And again –
- Extract the remainder: 521 % 26 = 1
- Map the remainder: A
- Divide the number: 521/26 = 20
And again –
- Extract the remainder: 20 % 26 = 20
- Map the remainder: T
- Divide the number: 20/26 = 0
Since the number is now 0, we are done!
2. Excel Column Title: Implementation
2.0. Code
class Solution: def convertToTitle(self, A): ans = "" while A: A -= 1 ans += chr(ord('A') + A % 26) A //= 26 return ans[::-1]
2.1. Complexity Analysis
- Time:
O(N)
, to iterate over all the elements in the string, where N is the length of the input string. - Space:
O(N)
, since reversing the string in python creates a new copy of it, and thus takes O(N) space.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Please write the proof.
This solution need an amendment for 2 digit number.
Please write a Proof for this