Add Digits
Easy · Math · Math · Number Theory · Simulation
Problem
You are given a non-negative integer num. Replace it with the sum of its decimal digits, and keep doing that until only one digit is left. Return that digit.
For example, 49 becomes 4 + 9 = 13, which becomes 1 + 3 = 4.
Can you do it in O(1) time, with no loop and no recursion?
Examples
Input: num = 49 Output: 4
4 + 9 = 13, then 1 + 3 = 4.
Input: num = 0 Output: 0
0 is already a single digit.
Input: num = 98765 Output: 8
9 + 8 + 7 + 6 + 5 = 35, then 3 + 5 = 8.
Constraints
- 0 <= num <= 2^31 - 1
Approaches
- Baseline: add the digits until one is left — time O(log num), space O(1)
Follow-up
The answer is called the digital root, and the modulo-9 rule behind it is the old "casting out nines" check for hand arithmetic. In base b the same argument works with b - 1 in place of 9. The use cases ask how many rounds the loop takes, and for the digital root of a number far too long for any integer type.
Related problems
Start free on Cariara · Coding problems · System design studio
