3 methods for python with explains


  • 51
    X
    1. Iteration method
          class Solution(object):
          def addDigits(self, num):
            """
            :type num: int
            :rtype: int
            """
            while(num >= 10):
                temp = 0
                while(num > 0):
                    temp += num % 10
                    num /= 10
                num = temp
            return num
    
    1. Digital Root

    this method depends on the truth:

    N=(a[0] * 1 + a[1] * 10 + ...a[n] * 10 ^n),and a[0]...a[n] are all between [0,9]

    we set M = a[0] + a[1] + ..a[n]

    and another truth is that:

    1 % 9 = 1

    10 % 9 = 1

    100 % 9 = 1

    so N % 9 = a[0] + a[1] + ..a[n]

    means N % 9 = M

    so N = M (% 9)

    as 9 % 9 = 0,so we can make (n - 1) % 9 + 1 to help us solve the problem when n is 9.as N is 9, ( 9 - 1) % 9 + 1 = 9

    class Solution(object):
    def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num == 0 : return 0
        else:return (num - 1) % 9 + 1

  • 2
    S

    Most people just mindlessly copy and paste the same answer as everyone else but at least you gave a great explanation, thanks!


  • 1
    S

    You can actually do the digital root method in one line:

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

  • 1
    W

    return (num % 9 or 9) if num else 0 better one liner


  • 1

    @wonderfuly
    No need for parentheses.

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

  • 0
    D

    thanks a lot!


  • 0
    B

    so N % 9 = a[0] + a[1] + ..a[n]

    I don't understand how this follows...


  • 5
    S

    @bmay Modulo properties

    1. associative over + : (a + b)%m = (a % m) + (b%m)
    2. For * : (a * b)%m = ((a % m) * (b%m)) % m
    3. (a % m)%m = (a % m)

    Applying this to N=(a[0] * 1 + a[1] * 10 + ...a[n] * 10 ^n)
    N % 9 = (a[0] * 1 + a[1] * 10 + ...a[n] * 10 ^n) % 9
    N % 9 = (a[0] * 1) % 9 + (a[1] * 10)%9 + ... + (a[n] * 10 ^n) % 9
    N % 9 = ((a[0] %9) * (1 % 9)) % 9 + ((a[1] %9) * (10 %9))%9 + ... + ( (a[n] %9) * (10 ^n % 9)) % 9

    Note that 10^k % 9 = 1, that simplifies
    N % 9 = ((a[0] %9) ) % 9 + ((a[1] %9))%9 + ... + ( (a[n] %9)) % 9
    N % 9 = (a[0] ) % 9 + (a[1])%9 + ... + ( a[n] ) % 9

    Note that a[i]<10, so a[i] % 9 = a[i], thus
    N % 9 = (a[0] + a[1] + ..a[n])


  • 0
    W

    class Solution(object):
    def addDigits(self, num):
    while num>=10:
    num=sum([int(x) for x in str(num)])
    return num


  • 0
    W

    '''class Solution(object):
    def addDigits(self, num):
    while num>=10:
    num=sum([int(x) for x in str(num)])
    return num'''


Log in to reply
 

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