258.md

Add Digits

Description

link

---

Solution

See Code

---

Code

# O(n)
class Solution:
    def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """
        if num < 10:
            return num
        
        nums = [int(n) for n in str(num)]
        
        return self.addDigits(sum(nums))


# O(1)
class Solution:
    def addDigits(self, num):
        """
        :type num: int
        :rtype: int
        """
        #follow up
        '''
        The essence of this problem is that 10^n ≡ 1 (mod 9), and thus a_n10^n + ... + a_110 + a_0 ≡ a_n + ... + a_1 + a_0 (mod 9).
        This process can be continued until a number less than 9 is gotten, i.e. num % 9.
        For any digit n, n = n % 9 unless n = 9.
        The only confusing case is n % 9 = 0, but addDigits(num) = 0 if and only if num = 0, otherwise it should be 9 in fact.
        '''
        rest = num % 9

        if num == 0:
            return 0

        if rest == 0:
            return 9

        return rest