thesarfo

Reference

Adding Digits (Digital Root)

Repeatedly summing a number's digits until one remains — and the O(1) modulo-9 shortcut that avoids simulating the process.

views 0

Given an integer num, repeatedly add all its digits until the result has only one digit, and return that result. (LeetCode 258)

Digit sum: for 38: 3 + 8 = 11, then 1 + 1 = 2. Stop once the result is a single digit.

Mathematical insight (digital root): there’s a shortcut formula that avoids simulating the summing process:

  • If num == 0, the result is 0.
  • If num % 9 == 0, the result is 9 (except when num is 0).
  • Otherwise, the result is num % 9.
class Solution {
    public int addDigits(int num) {
        if (num == 0) return 0; // Special case for 0
        if (num % 9 == 0) return 9; // If num is divisible by 9 and not 0
        return num % 9; // Return the digital root for non-multiples of 9
    }
}

For num = 38: 38 % 9 = 2, matching the manual sum (3+8=11, 1+1=2). For num = 0, the result is 0 directly.

Time complexity: O(1) — just a few arithmetic operations. Space complexity: O(1).

The modulo-9 shortcut works because of how digit sums relate to modulo arithmetic, particularly for numbers divisible by 9 — no need to sum digits repeatedly.