Jobs

Interviews

Discussions

Add Digits

Easy

Asked by:

More companies

71 views

Topics:

MathRecursionBit Manipulation

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 <= 2³¹ - 1

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

Try coding it in LeetCode

Add Digits

Easy

Asked by:

71 views

Topics:

MathRecursionBit Manipulation

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 <= 2³¹ - 1

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of the input number `num`?
What should I return if the input is zero?
Are we concerned about integer overflow during the repeated addition process?
Is there a restriction on using built-in functions or recursion for this problem?
Could you provide a few more example inputs and their expected outputs, especially at the boundaries of the input range?

Brute Force Solution

Approach

The brute force approach repeatedly sums the digits of a number until we get a single digit. We simply keep doing the addition over and over, reducing the number at each step until only one digit remains.

Here's how the algorithm would work step-by-step:

Start by adding up all the individual digits of the number.
If the result of this addition is a single-digit number, you're done. That's your answer.
If the result has more than one digit, take that result and add up its digits.
Keep repeating the process of adding digits until you eventually arrive at a single-digit number. That single digit is the final answer.

Code Implementation

def add_digits(number):
    while number > 9:
        sum_of_digits = 0

        # Iterate until we have summed all of the digits
        while number > 0:
            sum_of_digits += number % 10
            number //= 10

        # Assign the digit sum to number so the loop continues
        number = sum_of_digits

    # The number must be a single digit, so we return the single digit
    return number

Big(O) Analysis

Time Complexity

O(log n) – The number of iterations depends on how many times we need to sum the digits of a number until it becomes a single digit. In the worst case, a number 'n' will be repeatedly divided by 10 (approximately) during the digit summing process. Therefore, the number of iterations is proportional to the number of digits in n, which is log base 10 of n. The digit summing operation itself takes a time proportional to the number of digits, again log n. Because the number of summing operations is log n and each one takes log n the total run time is log(n)*log(n), but we only report the dominant behavior. Each digit-sum operation takes O(log n) time, and the number of iterations before reaching a single digit is at most another log n, but since the operations are technically sequential rather than nested the overall complexity is O(log n).

Space Complexity

O(1) – The algorithm repeatedly calculates the sum of digits until a single-digit number is obtained. No auxiliary data structures like arrays, lists, or hashmaps are used to store intermediate results. Only a few temporary variables are used to hold the sum of digits in each iteration. Therefore, the space required is constant and independent of the input number's size, which translates to O(1) space complexity.

Optimal Solution

Approach

The goal is to repeatedly add the digits of a number until we get a single-digit result. The most efficient way is to avoid any explicit addition by leveraging a mathematical property based on the number's relationship to multiples of nine.

Here's how the algorithm would work step-by-step:

If the number is zero, the answer is zero.
Otherwise, calculate the remainder when the number is divided by nine.
If the remainder is zero, the answer is nine.
If the remainder is not zero, the answer is the remainder.

Code Implementation

def add_digits(number):
    if number == 0:
        return 0

    # Use modulo 9 to find the digital root.
    remainder = number % 9

    # If divisible by 9, the digital root is 9.
    if remainder == 0:
        return 9

    # Otherwise, the remainder is the digital root.
    return remainder

Big(O) Analysis

Time Complexity

O(1) – The provided solution involves a fixed number of arithmetic operations regardless of the input number's size. We perform at most one modulo operation and a few conditional checks. Since the number of operations does not scale with the input number, the time complexity is constant, denoted as O(1).

Space Complexity

O(1) – The provided solution calculates the result using simple arithmetic operations (division and modulo) and conditional checks. It only uses a few constant space variables to store the input number, the remainder after division, and potentially the final result. No auxiliary data structures that scale with the input number N are used. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
Input is zero	Return zero directly as the sum of digits of 0 is 0.
Input is a single-digit number (1-9)	Return the number itself since it's already a single digit.
Large positive integer that could cause intermediate sums to overflow if not using 64 bit integers	Use 64-bit integers (long in Java, long long in C++) to accommodate potentially large intermediate sums, or use the congruence formula.
Maximum integer value (INT_MAX)	Handle the maximum integer value to avoid potential overflows in intermediate calculations, potentially using the congruence formula.
Negative Input	The problem states non-negative input; therefore, the solution should throw an error or return a predefined value (e.g., -1) indicating invalid input if it occurs.
Number with many 9s	A number with many 9s could lead to a long chain of additions; the congruence formula can address this directly.
Very small positive integer (1)	Return the input integer as it's already a single digit.
Integer close to zero (0)	Return the input integer as it's already a single digit.

Input is zero

How to Handle:

Return zero directly as the sum of digits of 0 is 0.

Input is a single-digit number (1-9)

How to Handle:

Return the number itself since it's already a single digit.

Large positive integer that could cause intermediate sums to overflow if not using 64 bit integers

How to Handle:

Use 64-bit integers (long in Java, long long in C++) to accommodate potentially large intermediate sums, or use the congruence formula.

Maximum integer value (INT_MAX)

How to Handle:

Handle the maximum integer value to avoid potential overflows in intermediate calculations, potentially using the congruence formula.

Negative Input

How to Handle:

The problem states non-negative input; therefore, the solution should throw an error or return a predefined value (e.g., -1) indicating invalid input if it occurs.

Number with many 9s

How to Handle:

A number with many 9s could lead to a long chain of additions; the congruence formula can address this directly.

Very small positive integer (1)

How to Handle:

Return the input integer as it's already a single digit.

Integer close to zero (0)

How to Handle:

Return the input integer as it's already a single digit.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of the input number `num`?
What should I return if the input is zero?
Are we concerned about integer overflow during the repeated addition process?
Is there a restriction on using built-in functions or recursion for this problem?
Could you provide a few more example inputs and their expected outputs, especially at the boundaries of the input range?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by adding up all the individual digits of the number.
If the result of this addition is a single-digit number, you're done. That's your answer.
If the result has more than one digit, take that result and add up its digits.
Keep repeating the process of adding digits until you eventually arrive at a single-digit number. That single digit is the final answer.

Code Implementation

def add_digits(number):
    while number > 9:
        sum_of_digits = 0

        # Iterate until we have summed all of the digits
        while number > 0:
            sum_of_digits += number % 10
            number //= 10

        # Assign the digit sum to number so the loop continues
        number = sum_of_digits

    # The number must be a single digit, so we return the single digit
    return number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

If the number is zero, the answer is zero.
Otherwise, calculate the remainder when the number is divided by nine.
If the remainder is zero, the answer is nine.
If the remainder is not zero, the answer is the remainder.

Code Implementation

def add_digits(number):
    if number == 0:
        return 0

    # Use modulo 9 to find the digital root.
    remainder = number % 9

    # If divisible by 9, the digital root is 9.
    if remainder == 0:
        return 9

    # Otherwise, the remainder is the digital root.
    return remainder

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero	Return zero directly as the sum of digits of 0 is 0.
Input is a single-digit number (1-9)	Return the number itself since it's already a single digit.
Large positive integer that could cause intermediate sums to overflow if not using 64 bit integers	Use 64-bit integers (long in Java, long long in C++) to accommodate potentially large intermediate sums, or use the congruence formula.
Maximum integer value (INT_MAX)	Handle the maximum integer value to avoid potential overflows in intermediate calculations, potentially using the congruence formula.
Negative Input	The problem states non-negative input; therefore, the solution should throw an error or return a predefined value (e.g., -1) indicating invalid input if it occurs.
Number with many 9s	A number with many 9s could lead to a long chain of additions; the congruence formula can address this directly.
Very small positive integer (1)	Return the input integer as it's already a single digit.
Integer close to zero (0)	Return the input integer as it's already a single digit.

Input is zero

How to Handle:

Return zero directly as the sum of digits of 0 is 0.

Input is a single-digit number (1-9)

How to Handle:

Return the number itself since it's already a single digit.

Large positive integer that could cause intermediate sums to overflow if not using 64 bit integers

How to Handle:

Use 64-bit integers (long in Java, long long in C++) to accommodate potentially large intermediate sums, or use the congruence formula.

Maximum integer value (INT_MAX)

How to Handle:

Handle the maximum integer value to avoid potential overflows in intermediate calculations, potentially using the congruence formula.

Negative Input

How to Handle:

The problem states non-negative input; therefore, the solution should throw an error or return a predefined value (e.g., -1) indicating invalid input if it occurs.

Number with many 9s

How to Handle:

A number with many 9s could lead to a long chain of additions; the congruence formula can address this directly.

Very small positive integer (1)

How to Handle:

Return the input integer as it's already a single digit.

Integer close to zero (0)

How to Handle:

Return the input integer as it's already a single digit.