The Add Digits problem is a fascinating mathematical problem that is often encountered in coding interviews and competitive programming platforms like LeetCode. This problem is based on the concept of “Digital Root” which has applications in number theory. In this comprehensive article, we will go through the problem statement, explain several approaches to solving it, and analyze their time and space complexities.
The problem can be stated as follows:
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
num = 38, the process is:
3 + 8 = 11,
1 + 1 = 2. Since
2has only one digit, return
num: a non-negative integer (0 <= num <= 2^31 – 1)
- Return the single-digit result after repeatedly adding the digits of the given number.
Approach 1: Naive Approach
- Convert the given integer to a string to easily access each digit.
- Sum the digits.
- If the sum is greater than or equal to 10, repeat steps 1-3.
- Otherwise, return the sum.
def addDigits(num): # Convert the number to string str_num = str(num) # Loop until the sum becomes a single digit while len(str_num) > 1: # Sum the digits sum_digits = sum(int(digit) for digit in str_num) # Convert the sum back to string str_num = str(sum_digits) # Return the sum as an integer return int(str_num)
The time complexity is O(N), where N is the number of digits in the number. In the worst case, this approach can be inefficient for very large numbers.
The space complexity is O(1), as only a constant amount of extra space is used.
Approach 2: Mathematical Approach (Digital Root)
This approach is based on the concept of the digital root. The digital root of a non-negative integer is the single-digit value obtained by an iterative process of summing digits, on each iteration using the result from the previous iteration to compute the digit sum. The digital root can be calculated using the formula:
digital_root = 1 + (num - 1) % 9
This formula directly calculates the digital root without the need to perform iterative sums.
def addDigits(num): if num == 0: return 0 return 1 + (num - 1) % 9
The time complexity is O(1) since the digital root is calculated using a constant-time mathematical formula.
The space complexity is also O(1), as only a constant amount of extra space is used.
Approach 3: Recursive Approach
This approach uses recursion to sum the digits until a single-digit number is obtained.
numis a single-digit number, return
- Otherwise, recursively call the function with the sum of the digits of
def addDigits(num): # Base case: if num is a single-digit number if num < 10: return num # Sum the digits and recursively call the function sum_digits = sum(int(digit) for digit in str(num)) return addDigits(sum_digits)
The time complexity is O(N), where N is the number of digits in the number.
The space complexity is O(N) due to the recursive call stack.
In this article, we explored the Add Digits problem on LeetCode and went through multiple approaches including the naive iterative approach, a mathematical approach based on the concept of digital root, and a recursive approach. The mathematical approach is the most efficient and elegant way to solve this problem.