Problem statement

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

Example 1

Input: num = 38
Output: 2
Explanation: 3+8 = 11, then 1+1 = 2. Two has one digit, so stop.

Example 2

Input: num = 0
Output: 0

Example 3

Input: num = 9999
Output: 9
Explanation: 9+9+9+9 = 36, then 3+6 = 9.

Constraints

• 0 <= num <= 2^31 - 1

Follow-up: Can you do it in O(1) time without any loop?

Hints for Add Digits

1. Hint 1

   The straightforward solution simply loops the summation until one digit remains.

2. Hint 2

   Summing digits never changes a number's remainder modulo 9, because 10 ≡ 1 (mod 9).

3. Hint 3

   That gives a closed form: 0 for 0, otherwise 1 + (num - 1) % 9.

How to solve Add Digits

Repeated digit summing computes the digital root, and a number and its digit sum are congruent modulo 9 because 10 ≡ 1 (mod 9). The answer is therefore num mod 9, with 9 in place of 0 for positive inputs.

Approach

1. Return 0 for num == 0.
2. Otherwise return 1 + (num - 1) % 9.

Why it works

Since 10^k ≡ 1 (mod 9), Σ dᵢ·10^i ≡ Σ dᵢ (mod 9) — digit summing preserves the residue mod 9. The process stops at a single digit, and among 1…9 only one digit has each residue, so the final digit is determined by num mod 9. The 1 + (num - 1) % 9 form maps residue 0 to 9 instead of 0.

Complexity

• Time — O(1)
• Space — O(1)

Pitfalls

• Writing num % 9 returns 0 for multiples of nine; the digital root of 18 is 9.
• The loop-until-one-digit version is also correct and only slightly slower — the closed form is the interview flourish.

Reference solution

Python

def addDigits(num: int) -> int:
    if num == 0:
        return 0
    return 1 + (num - 1) % 9

Java

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

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Multiply Two Linked Lists Easy
• Convert Binary Number in a Linked List to Integer Easy
• Check if Any Element Has Prime Frequency Easy
• Convert Date to Binary Easy
• Count Ways to Tile a 2 x N Floor Easy
• Find Nth Root of M Easy