258. Add Digits

Description

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

Example 1:

• Input: num = 38
• Output: 2
• Explanation: The process is
  38 –> 3 + 8 –> 11
  11 –> 1 + 1 –> 2
  Since 2 has only one digit, return it.

Example 2:

• Input: num = 0
• Output: 0

Constraints:

• 0 <= num <= 2³¹ - 1

Follow up: Could you do it without any loop/recursion in O(1) runtime?

💡 Hint 1:
A naive implementation of the above process is trivial. Could you come up with other methods?
💡 Hint 2:
What are all the possible results?
💡 Hint 3:
How do they occur, periodically or randomly?
💡 Hint 4:
You may find this Wikipedia article useful.

Submitted Code

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

class Solution(object):
    def addDigits(self, num):
        if num == 0:
            return 0
        
        return num - 9 * int(math.floor((num - 1) / 9))

Runtime: 0 ms | Beats 100.00%
Memory: 12.43 MB | Beats 49.41%

위키피디아의 공식을 참고해서 작성했다. 원리는 어떤 수를 9로 나눈 나머지는 그 자릿수 합을 9로 나눈 나머지와 같다는 것이다. 파이썬의 경우 num가 0일 때 -1 % 9의 결과가 8이 되기 때문에(항상 양수 나머지 반환) 예외 처리가 앞에 필요했다.

nums = 385

385 = 3⋅10² + 8⋅10¹ + 5⋅10⁰

10^k ≡ 1 mod 9 → 1

385 mod 9 = (3⋅1 + 8⋅1 + 5⋅1) mod 9 = 16 mod 9 = 7

return 7

Other Solutions

1st

class Solution(object):
    def addDigits(self, num):
        if num == 0 : return 0
        if num % 9 == 0 : return 9
        else : return (num % 9)       

time complexity: 𝑂(1)
space complexity: 𝑂(1)

num이 0이거나 9의 배수인 경우를 먼저 제외하면 num % 9으로 간단히 구할 수 있다.