Excel Column Number | InterviewBit | Solution Explained
Excel Column Number is a math problem on InterviewBit. I explain the solution using a simple approach. Problem Link.
This solution is the inverse of: Excel Column Title | InterviewBit | Solution Explained
0. Excel Column Number: Problem Discussion
0.0. IO Format
- a string of characters
- an integer, which is the equivalent of the input string
- characters given are capital English letters
- solution must be better than O(N) time and space each
The problem statement is weird, so let’s take a look at some examples.
- A -> 1
- B -> 2
- Z -> 26
- AA -> 27
- AZ -> 52
And so on.
1. Excel Column Number: Observations & Logic
Right away it is clear that we are dealing with characters that have different significances on each position.
For example, AB -> 28 since A = 1, but is at the position 1 – so we actually do 26 * 1 for A. Then, since B is at the position 0, we just add +2. This gives us the answer as 261 * 1 + 260 * 2.
If you notice, this is equivalent of saying 26i * val(X) where X is the character.
1.1. Formal Logic
- reverse the string:
AB -> BA
- keep a track of the index:
i = 0 -> 1 -> 2 -> ...
- find the value of a character:
val = ord(c) - ord('A') + 1
- then finally add to total:
26i + val
2. Excel Column Number: Implementation
class Solution: def titleToNumber(self, A): ans = 0 for i, c in enumerate(reversed(A)): ans += (26**i) * (ord(c)-ord('A') + 1) return ans
2.1. Complexity Analysis
O(N), to iterate over all the elements in the string, where N is the length of the input string.
O(N), since reversing the string in python creates a new copy of it, and thus takes O(N) space.
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