Problem Statement
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
Example:
代码语言：javascript复制Input: 38
Output: 2
Explanation: The process is like: 3 8 = 11, 1 1 = 2.
Since 2 has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?
Problem link
Video Tutorial
You can find the detailed video tutorial here
- Youtube
- B站
Thought Process
Just do a simple brute force simulation. Unless you know what a digital root is, beforehand solving it in O(1) cannot collect any useful signals from the candidate.
The triple bar equal is quite interesting. It means congruence. E.g., if you have two exactly same figures but one is rotated or clock points to 13 and 1, they are considered congruence (just like 13 and 1 mod by 12 are equal). In our example, it's about the mod result, e.g.,
Side note:
I am sharing with everyone on this problem just to express how useless this problem is... Honestly if someone ask you to solve this problem in O(1) time in a real interview, rethink joining that company. If you are an interviewer, please do yourself a favor not asking your candidate to solve it in O(1). It's an okay question to ask as a warm up just to calm your candidate down for the brute force solution.
Solutions
Brute force
Keep summing the each digit until the final number is < 10
1 public int addDigits(int num) {
2 assert num >= 0;
3
4 while (num / 10 > 0) {
5 num = this.calDigitSum(num);
6 }
7 return num;
8 }
9
10 private int calDigitSum(int num) {
11 int res = 0;
12
13 while (num > 0) {
14 res = num % 10;
15 num = num / 10;
16 }
17 return res;
18 }Time Complexity: O(N), N is the length of the digit
Space Complexity: O(1), No extra space is needed
Use the digital root formula
return (num - 1) % 9 1
Time Complexity: O(1)
Space Complexity: O(1)
References
- Congruence
- Digital Root
