### Problem Statement

Given a non-negative integer

`num`

, repeatedly add all its digits until the result has only one digit.**Example:**

Input:`38`

Output:2Explanation: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?

### 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.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 < 10Time 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)

## No comments:

## Post a Comment