248. Digital Root
A numerology app reduces any ticket number to one digit by repeatedly replacing the number with the sum of its decimal digits until only a single digit is left. Given a non-negative integer n, return that final single digit, known as the digital root of n.
For example, 4971 turns into 4+9+7+1 = 21, then 2+1 = 3, so the answer is 3. A number that already has one digit, including 0, is returned unchanged.
Simulating the process with loops is easy, but there is a neat pattern that gives the answer directly: the digital root only depends on the remainder of n after division by 9. Aim for a solution with O(1) time and O(1) extra space that uses no loops or recursion and does not convert the number to a string.
Example 1
- Input:
- n = 8675309
- Output:
- 2
- Explanation:
8+6+7+5+3+0+9 = 38, then 3+8 = 11, then 1+1 = 2, so the digital root is 2.
Example 2
- Input:
- n = 0
- Output:
- 0
- Explanation:
Zero is already a single digit, so it is its own digital root.
Example 3
- Input:
- n = 27
- Output:
- 9
- Explanation:
2+7 = 9, which is a single digit, so the answer is 9 (not 0).
Constraints
0 ≤ n ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(1)
- Space
- O(1)