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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Add Digits and Math problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →