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.
Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.