Problem¶

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

For example:

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

Input: columnNumber = 1
Output: “A”

Example 2:

Input: columnNumber = 28
Output: “AB”

Example 3:

Input: columnNumber = 701
Output: “ZY”

Constraints:

• 1 <= columnNumber <= 2**31 - 1

Solve¶

Borrow/Memo number modification¶

Like 171. Excel Sheet Column Number, this problem is a special base 26 to base 10 problem. That has character set ["A", "B", ..., "Z" ] with corresponds value [1,2,3,4,...,26] (it’s not including 0)

To make this easier to understand:

• "AB" = 27 can be presentation as [1, 2] (in special base 26)
• "ZY" = 701 can be presentation as [26, 25] (in special base 26)
• "Z" = 27 can be presentation as [26] (in special base 26)

def convertBase26Without0():
    ## Need to implement

While in normal base 26 (with 0), we have:

• "AB" = 27 can be presentation as [1, 2] (in normal base 26)
• "ZY" = 701 can be presentation as [1, 0, 25] (in normal base 26)
• "Z" = 26 can be presentation as [1, 0] (in normal base 26)

def convertBase26():
    remain = columnNumber
    curr = 0
    nums = []
    while remain:
        curr = remain % 26
        remain = remain // 26
        nums.apppend(curr)

After a “quick” analyze, I come to this conclusion

• This work the same as normal base 26, just without 0, instead, we have a new value 26
• This mean, instead of normal base 26 using 10 or [1, 0] -> we write Z or [26] instead
• Which it self is a modification: With any 0 we replace it with 26, and minus the next number by 1. Effectively to said that we are borrowing 26 value from the next number

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        r = columnNumber
        c = 0
        v = []
        memo = 0
        while r > 26:
            c = r % 26 + memo
            r = r // 26
            memo = 0
            if c <= 0:
                memo = -1
                v.append(26+c)
            else:
                v.append(c)
        res = ""
        ord_a = ord("A") - 1
        if r + memo > 0:
            res += chr(r + ord_a + memo)
        for i in v[::-1]:
            if i == "0":
                continue
            res += chr(i + ord_a)
        return res

Adding 1¶

This work the same as normal base 26, just without 0, instead, we have a new value 26

A more nature take is that we adding 1 for every number after modification, this can be achieve by taking 1 value from the remain and add it to curr

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        remain = columnNumber
        curr = 0
        ord_subA = ord("A") - 1
        res = ""
        while remain >= 26:
            curr = (remain - 1) % 26 + 1
            remain = (remain - 1) // 26
            res = chr(curr + ord_subA) + res

        if remain > 0:
            res = chr(remain + ord_subA) + res
        return res

By take a look at the best implementation, which done the same thing, just more compact:

class Solution:
    def convertToTitle(self, columnNumber: int) -> str:
        out = ''
        while columnNumber != 0:
            out = chr(ord('A') + (columnNumber - 1) % 26) + out
            columnNumber = (columnNumber - 1) // 26
        return out

C implementation¶

c

To prepare for creating char * (using maloc), we want to create a big enough char array, which need to be pre calculating.

So I just create a big enough memory size in stack, process the problem. Then re-copy the result’s value one by one to the heap allocation variable, already knowing it length and return.

As string in c is char[] or char * with NULL at end. I make sure to put NULL or 00000000 into the last element of the result title

char* convertToTitle(int columnNumber) {
    char nums[10] = {0};
    int length = 0;

    while (columnNumber > 0) {
        columnNumber--;
        nums[length] = 'A' + (columnNumber % 26);
        columnNumber /= 26;
        length++;
    }

    char* title = (char*)malloc((length + 1) * sizeof(char));

    title[length] = NULL;

    for (int i = length - 1; i >= 0; i --) {
        title[i] = nums[length - i - 1];
    }

    return title;
}