## Wednesday, July 24, 2019

### 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.

Could you do it without any loop/recursion in O(1) runtime?

### Video Tutorial

You can find the detailed video tutorial here

### 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

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)