Add Digits - Video Solutions

Problem Overview: Given a non‑negative integer num, repeatedly add its digits until the result becomes a single digit. For example, 38 → 3 + 8 = 11 → 1 + 1 = 2. The task is to compute this final single-digit result.

Approach 1: Iterative Digit Sum (Simulation) (Time: O(d * k), Space: O(1))

This approach directly simulates the process described in the problem. Extract digits using modulo (% 10) and division (/ 10), sum them, and repeat the process while the number has more than one digit. Each pass processes all digits once, so the cost depends on the number of digits d and how many iterations k are needed until a single digit remains. This method uses constant extra space and works in every language without relying on mathematical shortcuts. It’s a good baseline solution and demonstrates basic number manipulation techniques from simulation.

Approach 2: Digital Root Formula (Mathematical) (Time: O(1), Space: O(1))

The repeated digit sum has a well-known pattern in number theory. The result is called the digital root. For any positive integer, the digital root can be computed using the formula 1 + (num - 1) % 9. If num is 0, the result is 0. This works because numbers that differ by multiples of 9 share the same digital root. Instead of iterating through digits multiple times, the modulo operation jumps directly to the final answer. This turns the problem into a constant-time computation and avoids loops entirely.

Recommended for interviews: Start with the iterative simulation. It proves you understand digit extraction and the process defined in the problem. Then mention the digital root observation from math. Interviewers usually expect the O(1) formula as the optimal solution because it shows deeper insight into number properties rather than just implementing the steps literally.