Add Digits solution and explanation
Google
Infosys
9 more videos on this problem
Add Digits | LeetCode problem 258Technosage · 5:40 · 12K views
Add Digits | With Proof | (MICROSOFT, ADOBE) | Leetcode-258 | Live Code + ExplanationcodestorywithMIK · 17:59 · 5K views
Add Digits - LeetCode 258 - Python SolutionCode with Carter · 5:13 · 2K views
Leetcode - Add Digits (Math Explained)Timothy H Chang · 5:32 · 1K views
Add Digits | Leet code 258 | Theory explained + Python code | July Leet code challengeSai Anish Malla · 8:26 · 1K views
Add Digits| Leetcode 258| Live Coding session 🔥🔥🔥| 2 Approaches 💯💯 | String and MathsCoding Decoded · 6:38 · 962 views
Add Digits with O(1) runtime - LeetCode #258 - Python, JavaScript, Java, C++CodingNinja · 9:43 · 697 views
How to Solve "258 Add Digits" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 4:59 · 614 views
Add Digits - Leetcode 258 - PythonAlgorithms Casts · 7:11 · 591 views
Leetcode 258 - Add Digits - Python solutionData Engineering Studies · 3:18 · 533 views
The problem
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.
def add_digits(num):
while num >= 10:
sum = 0
while num > 0:
sum += num % 10
num //= 10
num = sum
return num
print(add_digits(38))public class AddDigitsIterative {
public static int addDigits(int num) {
while (num >= 10) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
num = sum;
}
return num;
}
public static void main(String[] args) {
int num = 38;
System.out.println(addDigits(num));
}
}#include <iostream>
int addDigits(int num) {
while (num >= 10) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
num = sum;
}
return num;
}
int main() {
int num = 38;
std::cout << addDigits(num) << std::endl;
return 0;
}function addDigits(num) {
while (num >= 10) {
let sum = 0;
while (num > 0) {
sum += num % 10;
num = Math.floor(num / 10);
}
num = sum;
}
return num;
}
console.log(addDigits(38));#include <stdio.h>
int addDigits(int num) {
while (num >= 10) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
num = sum;
}
return num;
}
int main() {
int num = 38;
printf("%d\n", addDigits(num));
return 0;
}using System;
public class AddDigitsIterative {
public static int AddDigits(int num) {
while (num >= 10) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
num = sum;
}
return num;
}
public static void Main() {
int num = 38;
Console.WriteLine(AddDigits(num));
}
}Python's implementation uses loops to compute the sum of the digits repeatedly until a single-digit number is obtained.
Space Complexity: O(1).
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.
def add_digits(num):
if num == 0:
return 0
return 9 if num % 9 == 0 else num % 9
print(add_digits(38))public class AddDigitsMath {
public static int addDigits(int num) {
if (num == 0) return 0;
return (num % 9 == 0) ? 9 : num % 9;
}
public static void main(String[] args) {
int num = 38;
System.out.println(addDigits(num));
}
}#include <iostream>
int addDigits(int num) {
if (num == 0) return 0;
if (num % 9 == 0) return 9;
return num % 9;
}
int main() {
int num = 38;
std::cout << addDigits(num) << std::endl;
return 0;
}function addDigits(num) {
if (num === 0) return 0;
return num % 9 === 0 ? 9 : num % 9;
}
console.log(addDigits(38));#include <stdio.h>
int addDigits(int num) {
if (num == 0) return 0;
if (num % 9 == 0) return 9;
return num % 9;
}
int main() {
int num = 38;
printf("%d\n", addDigits(num));
return 0;
}using System;
public class AddDigitsMath {
public static int AddDigits(int num) {
if (num == 0) return 0;
return (num % 9 == 0) ? 9 : num % 9;
}
public static void Main() {
int num = 38;
Console.WriteLine(AddDigits(num));
}
}Python leverages the modulo operation directly, taking advantage of the digit root principle for fast computation.
Space Complexity: O(1).
Approach 3: Default Approach
func addDigits(num int) int {
if num == 0 {
return 0
}
return (num-1)%9 + 1
}impl Solution {
pub fn add_digits(mut num: i32) -> i32 {
((num - 1) % 9) + 1
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n). Space Complexity: O(1). |
| Mathematical Approach | Time Complexity: O(1). Space Complexity: O(1). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When 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 Formula | O(1) | O(1) | Best choice for interviews and production due to constant-time computation |
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.