258. Add Digits

EasyLeetCode

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

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

0 <= i < j < k < arr.length

|arr[i] - arr[j]| <= a

|arr[j] - arr[k]| <= b

|arr[i] - arr[k]| <= c

Where |x| denotes the absolute value of x.

Return the number of good triplets.

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

How to solve the problem

1. Using recursion in return to recurse addDigits method.

2. Using another trick way or math way called Digital Root.

• For any number n, its digital root is:

• If n is 0, the digital root is 0

• If n is divisible by 9 and n ≠ 0, the digital root is 9

• In all other cases, the digital root is n % 9

Code

• Recursion

class Solution:
    def addDigits(self, num: int) -> int:
        sumDigits: int = 0

        if num < 10:
            return num

        while num > 0:
            sumDigits += num % 10
            num //= 10

        return self.addDigits(sumDigits)

• Digital Root

class Solution:
    def addDigits(self, num: int) -> int:
        digitRoot = 0

        if num == 0: return 0
        if num % 9 == 0: return 9
        else: return num % 9

Complexity

Time complexity:

• Recursion: O((log n)²)

• Digital Root: O(1)

Space complexity:

• Recursion: O(log n)

• Digital Root: O(1)