{x}
blog image

Add Digits

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?

Solution Explanation for LeetCode 258: Add Digits

This problem asks us to repeatedly sum the digits of a number until we get a single-digit result. The solutions presented leverage a mathematical property to achieve this in O(1) time complexity, avoiding explicit loops or recursion.

Mathematical Insight:

The digital root of a number is the recursive sum of its digits until a single digit is obtained. There's a direct formula to calculate the digital root:

  • If the number num is 0, the digital root is 0.
  • Otherwise, the digital root is (num - 1) % 9 + 1.

This formula works because of the properties of modular arithmetic and the fact that the remainder when a number is divided by 9 is invariant under the operation of summing its digits.

Code Explanation (Across Languages):

The provided solutions in Python, Java, C++, Go, and Rust all implement this formula directly. They check for the base case of num being 0 and then apply the formula otherwise.

Example Breakdown (Python):

class Solution:
    def addDigits(self, num: int) -> int:
        return 0 if num == 0 else (num - 1) % 9 + 1
  • return 0 if num == 0: This handles the special case where the input is 0. The digital root of 0 is 0.
  • else (num - 1) % 9 + 1: This applies the formula. (num - 1) % 9 finds the remainder when num - 1 is divided by 9. Adding 1 gives the correct digital root.

The other languages implement the same logic with minor syntactic differences.

Time and Space Complexity Analysis:

  • Time Complexity: O(1). The solution uses a constant number of operations regardless of the input number's size. This is because the modulo operation, subtraction, and addition are all constant-time operations.

  • Space Complexity: O(1). The solution uses a constant amount of extra space to store the result. No additional data structures are used that scale with the input size.

Why this is better than iterative or recursive approaches:

Iterative or recursive solutions would require looping or recursive calls, with the number of iterations or recursive calls potentially proportional to the number of digits in the input. This would result in O(log n) time complexity, where n is the input number. The provided O(1) solution is significantly more efficient, especially for very large input numbers.