#
# @lc app=leetcode id=258 lang=python3
#
# [258] Add Digits
#
# https://leetcode.com/problems/add-digits/description/
#
# algorithms
# Easy (59.18%)
# Likes:    1310
# Dislikes: 1351
# Total Accepted:    368.3K
# Total Submissions: 620.6K
# Testcase Example:  '38'
#
# 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^31 - 1
# 
# 
# 
# Follow up: Could you do it without any loop/recursion in O(1) runtime?
# 
#

# @lc code=start
class Solution:
    def addDigits(self, num: int) -> int:
        """
        DFS : 36 ms
        """
        if num // 10 == 0:
            return num
        r = 0
        while num // 10 != 0:
            r += num % 10
            num = num // 10
        return self.addDigits(r+num)

    def addDigits(self, num):
        """
        recursion: 32 ms
        """
        while num//10 != 0:
            r = 0
            while num // 10 != 0:
                r += num % 10
                num = num // 10
            num = r + num
        return num

# @lc code=end

so = Solution()
print(so.addDigits(0))

#
# @lc app=leetcode id=258 lang=python3
#
# [258] Add Digits
#
# https://leetcode.com/problems/add-digits/description/
#
# algorithms
# Easy (59.18%)
# Likes:    1310
# Dislikes: 1351
# Total Accepted:    368.3K
# Total Submissions: 620.6K
# Testcase Example:  '38'
#
# 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^31 - 1
# 
# 
# 
# Follow up: Could you do it without any loop/recursion in O(1) runtime?
# 
#

# @lc code=start
class Solution:
    def addDigits(self, num: int) -> int:
        """
        DFS : 36 ms
        """
        if num // 10 == 0:
            return num
        r = 0
        while num // 10 != 0:
            r += num % 10
            num = num // 10
        return self.addDigits(r+num)

    def addDigits(self, num):
        """
        recursion: 32 ms
        """
        while num//10 != 0:
            r = 0
            while num // 10 != 0:
                r += num % 10
                num = num // 10
            num = r + num
        return num

# @lc code=end

so = Solution()
print(so.addDigits(0))

# # @lc app=leetcode id=258 lang=python3 # # [258] Add Digits # # https://leetcode.com/problems/add-digits/description/ # # algorithms # Easy (59.18%) # Likes:    1310 # Dislikes: 1351 # Total Accepted:    368.3K # Total Submissions: 620.6K # Testcase Example:  '38' # # 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^31 - 1 # # # # Follow up: Could you do it without any loop/recursion in O(1) runtime? # # # @lc code=start DFS : 36 ms recursion: 32 ms # @lc code=end