Repeated Digit Sum
Problem
Take a non-negative whole number and add up its decimal digits. If the result has more than one digit, add up its digits again, and keep going until a single digit remains. Return that digit, ideally without looping at all.
Examples
Input: n = 38
Output: 2
Why: 3 + 8 = 11, then 1 + 1 = 2Input: n = 99999
Output: 9
Why: the digits add to 45, and 4 + 5 = 9Input: n = 0
Output: 0
Why: edge case, zero is already one digit and the only number that ends at 0Hints
0 / 3
Simulating the process is easy. The interesting question is whether the final digit can be predicted from the number directly.
Ten leaves a remainder of one when divided by nine, and so does every power of ten. Think about what that says about a number and the sum of its digits.
A number and its digit sum leave the same remainder modulo nine, so the final digit is fixed by n modulo 9. Map a remainder of zero to 9 for positive numbers and handle n equal to 0 separately; the expression 1 plus (n minus 1) modulo 9 does both mappings at once.
Solution
Every power of ten is one more than a multiple of nine, so a number and the sum of its digits leave the same remainder modulo nine, and that remainder survives every round of the process. The final single digit is therefore the one digit from 1 to 9 with the same remainder as n, which is 1 plus (n minus 1) modulo 9, with zero as the only number that ends at 0. No loop is needed. Time and space are O(1).
def digit_root(n):
if n == 0:
return 0 # the only number whose digits sum to 0
return 1 + (n - 1) % 9 # digit sums preserve the remainder mod 9
print(digit_root(38)) # -> 2
print(digit_root(99999)) # -> 9
print(digit_root(0)) # -> 0
print(digit_root(9)) # -> 9Stuck on the idea rather than the code? Modular Arithmetic covers it.