How do you approach Add Digits?

A straightforward loop works: while num has more than one digit, replace it with its digit sum.

What is the time complexity of Add Digits?

Time complexity: O(1). Space complexity: O(1).

What are common mistakes on Add Digits?

Overflowing at an intermediate step even though the final answer fits. Assuming a modulo is non-negative. In most languages -1 % n is negative, which breaks cyclic indexing. Testing floating-point values for exact equality where integer arithmetic would have been exact.

gitGood.dev

← Back to problems

Add Digits

EasyAlgorithms

Description

Given a non-negative integer `num`, repeatedly add all its digits until the result has only one digit, and return that digit. **Follow up:** Can you do it without any loop or recursion, in O(1) time?

Example 1

Input: num = 38

Output: 2

Explanation: 38 -> 3 + 8 = 11 -> 1 + 1 = 2. Since 2 has only one digit, return it.

Example 2

Input: num = 0

Output: 0

Example 3

Input: num = 9

Output: 9

Constraints

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

Add Digits: approach, complexity and pitfalls

An easy math problem, graded against 7 test cases (4 of them hidden).

The pattern: Math

Number theory, digit manipulation, and closed-form reasoning.

Reach for it when you see: Primes, digits, base conversion, or a problem with a formula hiding behind it.

More Mathproblems →

If you are stuck

Show the 3-step hint ladder

A straightforward loop works: while num has more than one digit, replace it with its digit sum.
Look at the answers for 1..18: 1,2,...,9,1,2,...,9. The result cycles with period 9 - this is the 'digital root'.
Because a number is congruent to its digit sum mod 9, the answer is 0 when num is 0, otherwise 1 + (num - 1) % 9.

The optimal approach

Show the approach: Digital Root Formula

Summing decimal digits preserves the value mod 9 (since 10 ≡ 1 mod 9), so repeating it converges to the number's residue class. The closed form is `0` for `num = 0` and `1 + (num - 1) % 9` otherwise - the `-1/+1` shift maps multiples of 9 to 9 instead of 0.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Math mistakes

These apply to the pattern as a whole, not just this problem.

Overflowing at an intermediate step even though the final answer fits.
Assuming a modulo is non-negative. In most languages `-1 % n` is negative, which breaks cyclic indexing.
Testing floating-point values for exact equality where integer arithmetic would have been exact.