LeetCode 168. Excel Sheet Column Title

September 12, 2020

This looks like we're converting decimal numbers to $base_{26}$ numbers represented with characters.

We can do at best $O(n)$ since, even if we're doing something fancy like bitwise operations, we need to create/convert every character of the output.

Here's a naive $O(n)$ solution:

Step through [ $26^i$ for $i$ in $\{0...magnitude\}$ ], dividing and finding the remainder for each.
There's a special case for 0's since they don't exist here ( $B0$ is actually $AZ$ ).

Is there a faster bitwise solution? I don't think so? If we were working with a base that was a power of 2, we could, but $base_{26}$ won't work for that.

import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertEqual(self.s.convertToTitle(703), "AAA")
        self.assertEqual(self.s.convertToTitle(1), "A")
        self.assertEqual(self.s.convertToTitle(26), "Z")
        self.assertEqual(self.s.convertToTitle(28), "AB")
        self.assertEqual(self.s.convertToTitle(52), "AZ")
        self.assertEqual(self.s.convertToTitle(701), "ZY")

class Solution:

    def convertToTitle(self, n: int) -> str:
        title = ""
        while n > 0:
            mod = n % 26
            n -= mod
            n //= 26
            conv = mod
            if mod == 0 and n > 0:
                # Do a reverse-carry(?) for Z's / to accommodate the lack of 0s.
                n -= 1
                conv = 26
            # Convert 1-26 to ascii character codes (offset of 64 because 'A' is 65).
            title += chr(64 + conv)
        return title[::-1]

if __name__ == "__main__":
    unittest.main()