Skip to main content

258. Add Digits

easy

Sum the digits of an integer and repeat until the result is a single digit. The textbook digital-root problem — solvable by simulation, or in O(1) via the modulo-9 identity.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it. Follow up: Could you do it without any loop/recursion in O(1) runtime?

Constraints

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

Examples

Example 1

Input
num = 38
Output
2

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

Example 2

Input
num = 0
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Simulation: while num >= 10, replace num with the sum of its digits. Return num.

Hint 2

Math shortcut: this is the digital root, equal to 1 + (num - 1) mod 9 for num > 0, and 0 for num = 0.

Hint 3

Why: each time you replace num with digit-sum, you subtract a multiple of 9 (since 10^k - 1 is divisible by 9). So num and digit-sum are congruent mod 9.

Hint 4

Iterating to a single digit lands you on either 0 (if num == 0) or one of 1..9, which is exactly the digital root.

Solution approach

Reveal approach

Mathematical O(1) approach using the digital-root formula: if num == 0, return 0; otherwise return 1 + (num - 1) % 9. The expression handles the edge case where num is a positive multiple of 9 (digital root is 9, not 0) cleanly: for num = 9, (9-1) % 9 = 8, plus 1 is 9. Simulation alternative: while num >= 10, set num = sum of its digits using % 10 and / 10 loop; return num. The simulation is O(log num) per pass with O(log log num) passes — effectively constant for any 32-bit int. Both are valid interview answers; the digital-root formula is the 'wow' answer.

Complexity

Time
O(1)
Space
O(1)

Related patterns

  • math

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Bloomberg

More Math practice problems

See all Math problems →