Baozi Training Leetcode Solution 258: Add Digits

Problem Statement

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

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