Add Digits

easy math digit dp number theory

Problem

Repeatedly sum the digits of a non-negative integer until the result has one digit. Return that digit.

Inputnum = 38

Output2

3+8=11 → 1+1=2 (or directly: 1 + (38-1) mod 9 = 2).

num

def add_digits(num):
    if num == 0: return 0
    return 1 + (num - 1) % 9

function addDigits(num) {
  if (num === 0) return 0;
  return 1 + (num - 1) % 9;
}

class Solution {
    public int addDigits(int num) {
        if (num == 0) return 0;
        return 1 + (num - 1) % 9;
    }
}

int addDigits(int num) {
    if (num == 0) return 0;
    return 1 + (num - 1) % 9;
}

Explanation

The problem asks us to keep summing a number's digits until one digit is left. The surprising part is that we can skip all that looping and get the answer with a single formula.

That single-digit result is called the digital root, and there's a known fact from number theory: the digital root of a positive number is 1 + (num - 1) % 9. The only special case is 0, which simply returns 0.

Why does it work? Repeatedly summing digits never changes a number's remainder mod 9, because 10, 100, and so on are all 1 more than a multiple of 9. So the final single digit equals the number's value mod 9, with the small (num-1)%9 + 1 twist so that multiples of 9 land on 9 instead of 0.

Example: num = 38. The slow way is 3+8=11, then 1+1=2. The formula gives 1 + (38-1) % 9 = 1 + 37 % 9 = 1 + 1 = 2. Same answer, no loop.

Time: O(1) Space: O(1)