168.Excel Sheet Column Title

Tags: [recursion], [prefix], [Math], [Trick], [mod]

Com: {fb}

Link: https://leetcode.com/problems/excel-sheet-column-title/#/description

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 ->AB

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases.

Better Understanding Solution:

class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n <= 0:
            return ''

        result = []
        while n > 0:
            n -= 1
            result.append(chr(ord('A') + n % 26))
            n /= 26

        result.reverse()
        return ''.join(result)

Solution: Mod, Trick

class Solution(object):
    def convertToTitle(self, n):
        """
        :type n: int
        :rtype: str
        """
        # base case
        if not n:
            return ''

        return self.convertToTitle((n - 1) / 26) + chr(ord('A') + (n - 1) % 26)

Revelation:

• Using the recursion to build the prefix, because each time we can get (n - 1) % 26, which is in the range[0, 25].
• To convert the n based on 0, we should first do n - 1, then do '/26' and '%26'.

Note:

• Time complexity = O(logn [based on 26]), because each time we divide the n by 26, then give it to next level recursion.