0 MS 5 LINES C++


  • 6
    C
    string convertToTitle(int n) {
        string res;
        while(n>=1){
            res=(char)('A'+(n-1)%26)+res;
            n=(n-1)/26;
        }
        return res;
    }

  • 0
    L

    I am still a bit confused about the "n-1". When I write the code without "n-1", the output of 26 is wrong but correct with "n--". Can anybody explain it to me?


  • 0
    R

    You can use the following code..both correct. It is just decrements of one ASCII value!!!
    class Solution {
    public:
    string convertToTitle(int n) {
    string str;
    for (; n>0; n=(n-1)/26)
    //str = (char)(--n%26 + 'A') + str;
    str = (char)('A' +(n-1)%26) + str;
    return str;
    }
    };


  • 0
    F

    the reason why this happen lies in the number base convert:
    Consider for given number X, we can rewrite (X)p = Anp^n + ... + A1p^1+A0, where p is new base, and for any Ai: 0<=Ai<=p-1, for example (3)2 = 1 * 2^1 + 1 * 1 means convert 10 based 3 to 2 based 3.
    ok, for this question, the tricky part is there is no 0 element, so, if you want to convert from 10 based to this special based count, you need to create 0 element in this base, How? minus will helps.
    See proof below, where assuming p is the based required in question:
    (X)p = Anp^n + ... + A1p^1+A0, p = 26, 1<=Ai<=26
    (X-1)p Anp^n + ... + A1p^1+(A0-1), p = 26, 1<=Ai-1<=26, i >=1, 0<=A0<=25
    so, in this step, we can use simple way to get A0: values (X-1)%26 maps from char 'A' to 'Z', where 'A' is 0 element.
    then, by (X-1)/26, we get smaller problem as below:
    ((X-1)/26)p = An*p^n + ... + A1, for 1<=Ai<=26
    Then recursive happens, by induction, you can prove this is correct ( base case n = 0, then it is '')
    SO the algorithm is clear, I rewrite it in python as below, hope this could help:
    def init(self):
    self.__base = tuple(string.uppercase[:])

    def recv_convertToTitle(self, n):
        return '' if n == 0 else self.recv_convertToTitle(( (n - 1) // 26)) + self.__base[(n - 1) % 26]
    

  • 0
    F

    consider this is simple number base convert question, then it is more easy to do


  • 0
    O

    wow nice mathematical explanation, though it's a little bit hard to read ha!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.