748. Digital Root (Recursive Digit Sum)

Given a non-negative integer n, repeatedly sum its digits until a single digit remains, and return that single digit. This final value is called the digital root of n.

Solve it using recursion: sum the digits once, then recurse on the result until it is a single digit.

Input: A single non-negative integer n.

Output: A single integer (0-9) — the digital root of n.

Examples

Input: 12345
Output: 6
Explanation: 1+2+3+4+5=15 → 1+5=6.

Input: 0
Output: 0
Explanation: Already a single digit.

Input: 99999
Output: 9
Explanation: Sum=45 → 4+5=9.

Constraints

• 0 <= n <= 2000000000

Asked by