Python constant time with explanation


  • 0
    K

    The naive approach is simply to turn the integer into a string, split the string into a list of digits, add up the digits, and recursively call addDigits on the resulting sum.

        def addDigits(self, num):
            if num < 10:
                return num
            return self.addDigits(sum([int(d) for d in list(str(num))]))
    

    However, this isn't constant time (not quite sure what time complexity it is... I think O(log(num))).

    To come up with a constant time solution, it's instructive to consider the example input,

    num = 41
    

    The 2 recursive calls of the naive addDigits on this looks like:

    Call 1: 41
    Call 2: 5
    

    Notice that we wouldn't be changing our results if we had 32 instead of 41 (a difference of 9). The results also wouldn't change if we had 23 instead of 41 (a difference of 18), or 14 instead of 41 (a difference of 27). Finally, we could've simply had 5 instead of the 41 (a difference of 36).

    This gives us the hint that, in fact, we can take away as many 9's from a number as possible, without affecting the sum of its digits!

    This leads us to the core of the function:

    final_sum(digits of num) = num%9
    

    One case to be wary of: What happens when num=45? The sum of 4 and 5 is 9... yet the current function gives us 0! This can easily be taken care of by adding a conditional to our function:

    if num%9==0:
        return 9
    

    This may lead to speculations of "what happens when the sum really is 0? We wouldn't want to return 9!" Well, the sum of the digits of any number is 0 if and only if the original number was 0 itself. So this is taken care of via another conditional:

    if num==0:
        return 0
    

    The resulting function looks like:

        def addDigits(self, num):
            if num==0:
                return 0
            temp = num%9
            if temp==0:
                return 9
            else:
                return temp
    

    Or more concisely,

        def addDigits(self, num):
            return num if not num else num%9 if num%9 else 9
    

Log in to reply
 

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