Solution For Add Digits

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.

Step by Step Implementation For Add Digits

public int addDigits(int num) {
    
    // edge case: if num is 0, return 0
    if (num == 0) {
        return 0;
    }
    
    // initialize sum to 0
    int sum = 0;
    
    // loop through each digit in num
    // for each digit, add it to sum
    // then update num to be num / 10
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    
    // if sum > 9, call addDigits(sum) recursively
    // otherwise, return sum
    return sum > 9 ? addDigits(sum) : sum;
}

def addDigits(num): 

# Base case 
if num == 0: 
return 0

# A simple solution is to process digits one by one. 
# We add the current digit to a variable 
# 'sum' and process the remaining digits recursively. 
if num % 9 == 0: 
return 9

else: 
return num % 9

var addDigits = function(num) {
    
    // we need to keep track of the sum
    // and the number of digits in the sum
    let sum = 0;
    let numDigits = 0;
    
    // we also need to keep track of the number of digits in the input number
    let numLength = num.toString().length;
    
    // this while loop will keep going until the sum has the same number of digits as the input number
    while (numDigits < numLength) {
        
        // we get the last digit of the number by using the modulus operator
        let lastDigit = num % 10;
        
        // we add the last digit to the sum
        sum += lastDigit;
        
        // we remove the last digit from the number by dividing by 10 and truncating the decimal
        num = Math.trunc(num / 10);
        
        // we increment the number of digits in the sum
        numDigits++;
    }
    
    // if the sum has more digits than the input number, we need to run the function again with the sum as the input
    if (numDigits > numLength) {
        return addDigits(sum);
    }
    
    // otherwise, we return the sum
    return sum;
    
};

int addDigits(int num) {
    
    // base case
    if (num < 10) {
        return num;
    }
    
    // recursive case
    else {
        return addDigits(num % 10 + addDigits(num / 10));
    }
}

public int AddDigits(int num) 
{ 
    if (num == 0) 
        return 0; 
    if (num % 9 == 0) 
        return 9; 
    else
        return num % 9; 
}