Leetcode – Add Digits Solution in Python

Spread the love

Introduction

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.

Problem Statement

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.

For example:

  • Given num = 38, the process is: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return 2.

Input

  • num: a non-negative integer (0 <= num <= 2^31 – 1)

Output

  • Return the single-digit result after repeatedly adding the digits of the given number.

Approach 1: Naive Approach

  1. Convert the given integer to a string to easily access each digit.
  2. Sum the digits.
  3. If the sum is greater than or equal to 10, repeat steps 1-3.
  4. 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)

Time Complexity

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.

Space Complexity

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

Time Complexity

The time complexity is O(1) since the digital root is calculated using a constant-time mathematical formula.

Space Complexity

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.

  1. If num is a single-digit number, return num.
  2. Otherwise, recursively call the function with the sum of the digits of num.
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)

Time Complexity

The time complexity is O(N), where N is the number of digits in the number.

Space Complexity

The space complexity is O(N) due to the recursive call stack.

Conclusion

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.

Leave a Reply