258. Add Digits - Detailed Explanation

Problem Statement

Given a non‑negative integer num, repeatedly add all its digits until the result has only one digit, and return that digit

Examples

Input: 38
Output: 2
Explanation: 3 + 8 = 11 → 1 + 1 = 2
Input: 0
Output: 0
Explanation: No summation needed, already one digit
Input: 12345
Output: 6
Explanation: 1+2+3+4+5 = 15 → 1+5 = 6

Constraints

0 ≤ num ≤ 2³¹ − 1
Must run in O(1) extra space for the optimal solution

Hints

Think about what happens when you sum digits repeatedly: can you jump straight to the final result without the loop?
Try writing a helper to sum digits once. How many times would you need to call it for the worst case?

Brute Force Approach

Explanation

Keep summing the digits of num until it becomes a single digit. You can convert the number to a string or extract digits by mod/divide operations.

Step‑by‑step Walkthrough

If num < 10, return num
Else:
- Extract each digit (e.g. num % 10, then num /= 10)
- Sum them into sum
- Replace num with sum and repeat

Visual Example

num = 38
sum digits: 3 + 8 = 11
num = 11
sum digits: 1 + 1 = 2
num = 2 → single digit → return 2

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time O(log n × d) where d is number of digits (since each summation is O(d) and you repeat ~log₁₀(n) times)
Space O(1) extra

Optimal Approach (Digital Root)

Explanation

There is a mathematical shortcut: the result is 1 + (num - 1) % 9 for num > 0, and 0 when num == 0. This follows from properties of congruence modulo 9.

Step‑by‑step Walkthrough

If num == 0, return 0
Else compute result = 1 + (num - 1) % 9

Visual Example

num = 38
(38 - 1) % 9 + 1 = 37 % 9 + 1 = 1 + 1 = 2

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time O(1)
Space O(1)

Common Mistakes

Forgetting to handle num == 0 (should return 0)
Using recursive digit‑sum without stopping condition, leading to stack overflow on very large inputs
Misapplying the modulo formula for numbers exactly divisible by 9