Skip to main content
Talentd

Add Digits - Solution & Explanation

EasyMathSimulationNumber Theory9 min readAsked at: Amazon, Microsoft, Meta +7
Practice this problem

Problem Statement

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

 

Example 1:

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

Example 2:

Input: num = 0
Output: 0

 

Constraints:

  • 0 <= num <= 231 - 1

 

Follow up: Could you do it without any loop/recursion in O(1) runtime?

Approach Overview

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.

Approach 1: Iterative Approach

The iterative approach involves summing the digits of the number repeatedly until the sum becomes a single-digit number. This is a straightforward approach and uses basic loops to repeatedly process the digits of the number.

The function addDigits takes an integer which it divides into its individual digits by taking the modulo and integer division operations. It sums these digits and repeats the process until the result is a single digit.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the number of digits in the number. This is because each iteration sums the digits.
Space Complexity: O(1) because we only use a constant amount of extra space.
Try this approach in the editor →

Approach 2: Mathematical Approach

The mathematical approach leverages a known number theory result related to digit root which can be deduced using modulo 9 arithmetic. The result for the repeated digit sum is equivalent to the number modulo 9, except that when the number is zero it should remain zero.

This C solution uses modulo 9 to calculate the digit root. This gives us a constant time solution which is highly efficient.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1).
Space Complexity: O(1).
Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoRust

Python

Java

C++

Go

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative ApproachTime Complexity: O(n) where n is the number of digits in the number. This is because each iteration sums the digits.
Space Complexity: O(1) because we only use a constant amount of extra space.
Mathematical ApproachTime Complexity: O(1).
Space Complexity: O(1).
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Digit Sum (Simulation)O(d * k)O(1)When implementing the process directly or when mathematical shortcuts are not known
Digital Root Mathematical FormulaO(1)O(1)Best choice for interviews and production due to constant-time computation

Video Solution

Add Digits | LeetCode problem 258 • Technosage • 12,023 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Add Digits easy or hard?
Add Digits is classified as an Easy problem on LeetCode with a high acceptance rate. The simulation solution is straightforward, but recognizing the digital root formula demonstrates stronger mathematical insight.
How to solve Add Digits in O(1)?
Use the digital root property from number theory. If num is not zero, compute 1 + (num - 1) % 9. This formula directly returns the final digit produced by repeatedly summing digits, eliminating loops or recursion.
What is the best approach for Add Digits?
The best approach is the mathematical digital root formula: 1 + (num - 1) % 9 for num > 0, and 0 if num is 0. It computes the final single digit in constant time without repeatedly summing digits. This reduces the problem from multiple iterations to a single modulo operation.
What data structure is used in Add Digits?
No special data structure is required. The solution relies on arithmetic operations such as modulo and division to extract digits. The optimal version uses a number theory formula instead of any data structure.
What is the time complexity of Add Digits?
The optimal digital root approach runs in O(1) time and O(1) space because it uses a direct mathematical formula. A straightforward simulation that repeatedly sums digits takes O(d * k) time, where d is the number of digits and k is the number of iterations until a single digit remains.
Add Digits Python or Java solution approach?
In Python or Java, the simulation approach repeatedly extracts digits using % 10 and divides the number by 10 until one digit remains. The optimal implementation uses the digital root formula: return 0 if num == 0, otherwise return 1 + (num - 1) % 9.
Is Add Digits asked at Google, Amazon, or Meta?
Add Digits is a common easy-level screening problem used by companies like Google, Amazon, and Meta to test basic math reasoning and number manipulation. The problem often checks whether candidates recognize the digital root pattern rather than only implementing simulation.

Ready to solve this problem?

Practice Add Digits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Alternating Digit Sum

Next

Calculate Digit Sum of a String