#258
Add Digits
Easy Digital root
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Keep replacing a number with the sum of its digits until only one digit is left, and return that digit.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: keep summing digits until one digit is left (the "digital root").
Why this works: a number and its digit sum have the same remainder mod 9, so the final digit is fixed by num mod 9, with multiples of 9 giving 9.
Example: num = 38
3 + 8 = 11 → 1 + 1 = 2formula: 1 + (38 - 1) % 9 = 1 + 1 = 2 ✓
✦Hints open one at a time
The simple loop works. Can you find an O(1) formula?
A number and its digit sum leave the same remainder when divided by 9.
↗Approach
This is the digital root. For num = 0 the answer is 0; otherwise it is 1 + (num - 1) % 9, which maps multiples of 9 to 9 instead of 0.
</>Solution (Java)
class Solution {
public int addDigits(int num) {
if (num == 0) return 0;
return 1 + (num - 1) % 9; // digital root formula
}
}!Common mistake
Using num % 9 directly, which gives 0 for 9, 18, 27… instead of 9.
Complexity
- Time: O(1).
- Space: O(1).
