Add Digits - Leetcode Solution

Problem Statement:

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Input: 38 Output: 2 Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Solution:

The problem statement states that we have to keep adding all the digits until we are left with a single digit. For example, for the number 38, we need to first add 3 and 8, which gives us 11. Now we need to add 1 and 1, which gives us the desired result of 2.

We can easily solve this problem using a while loop. We will keep on adding all the digits of the number until we are left with a single digit. We can sum up all the digits using the modulo operator and integer division.

Algorithm:

1. Define a variable sum as 0.
2. Define a while loop that continues until the given number is reduced to a single digit.
3. In each iteration of the while loop, compute the sum of all the digits of the given number by using the modulo operator and integer division.
4. Once the sum is computed, update the value of the given number as the sum.
5. Return the final sum after the while loop terminates.

Python Code:

def addDigits(num): while num > 9: sum = 0 while num > 0: sum += num % 10 num //= 10 num = sum return num

Explanation of Code:

We have defined the function addDigits that takes a non-negative integer as input. We have defined two loops to add all the digits until we are left with a single digit.

In the outer while loop, we have check if the given number is greater than 9. If it is, we enter the while loop. In each iteration of the outer while loop, we compute the sum of all the digits of the given number by using the modulo operator and integer division.

After calculating the sum of digits, we update the value of the given number as the sum. The inner while loop will continue until all the digits are added and we are left with a single-digit number.

Once the outer while loop terminates, we return the final sum.

Complexity Analysis:

Time complexity: The time complexity of this solution is O(n), where n is the number of digits in the input number.

Space complexity: The space complexity of the solution is O(1), as we are not using any extra data structure to store the digits of the number.

1