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

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