258. Add Digits
EasyLeetCodeGiven 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 ≤ 231 - 1
How to solve the problem
Using recursion in
return
to recurseaddDigits
method.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)
Comments
No comments yet. Be the first to comment!