Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/258.html
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 <= 231 - 1
Follow up: Could you do it without any loop/recursion in O(1)
runtime?
Algorithm
Let’s first observe all the roots from 1 to 20:
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 1
11 2
12 3
13 4
14 5
15 6
16 7
17 8
18 9
19 1
20 2
Draw a rule, every 9 a cycle, all roots of numbers greater than 9 take the remainder of 9, so for the number equal to 9 to take the remainder of 9 is 0, in order to get itself, and also need to be greater than The number of 9 applies, we use the expression (n-1)%9+1
to cover all cases.
There is another special case that needs to be considered. When num is 0, then there will be a situation of -1% 9, need to make an additional judgment.
Code
-
class Solution { public int addDigits(int num) { return (num == 0) ? 0 : (num - 1) % 9 + 1; } }; ############ class Solution { public int addDigits(int num) { return (num - 1) % 9 + 1; } }
-
// OJ: https://leetcode.com/problems/add-digits/ // Time: O(lgN) // Space: O(1) class Solution { public: int addDigits(int n) { while (n > 9) { int next = 0; for (; n; n /= 10) next += n % 10; n = next; } return n; } };
-
class Solution: def addDigits(self, num: int) -> int: return 0 if num == 0 else (num - 1) % 9 + 1 ############ class Solution(object): def addDigits(self, num): """ :type num: int :rtype: int """ if num < 10: return num return 1 + (num - 1) % 9
-
func addDigits(num int) int { if num == 0 { return 0 } return (num-1)%9 + 1 }
-
impl Solution { pub fn add_digits(mut num: i32) -> i32 { (num - 1) % 9 + 1 } }