Thursday, 28 March 2019

Find sum of digits of a number until sum becomes single digit

Find sum of digits of a number until sum becomes single digit.

Given a non-negative integer, repeatedly add all its digits until the result has only one digit.
Lets understand what is the input and the expected output.


Algorithm 

We will see both iterative and recursive approach.

 Modulo: We will modulo the number by 10 to get the last digit of number and sum it in count variable.
Divide: Get the rest of the number except last digit by dividing the number by 10.
Check: Check the number becomes 0, if yes, it means we get the sum of all the digits of number,  if not, repeat until number becomes 0.

 Repeat the steps:
Above steps needs to be executed for getting the sum of the number. once we get the sum, we just need to check if sum is > 10, if yes, than it is more than single digit number, so repeat the above steps for the new number which is the sum we got until it becomes 0.

Find sum of digits of a number until sum becomes single digit in Java
package com.javabypatel.misc;

/*

Input: 100
Output: 1 (1+0+0 = 1) -> 1 is single digit, stop

Input: 12345
Output: 6
        (1+2+3+4+5 = 15) -> 15 is two digit, so repeat the steps for 15
        (1+5 = 6) -> 6 is single digit, stop

Input: 9998
Output: 8
        (9+9+9+8 = 35) -> 35 is two digit, so repeat the steps for 35
        (3+5 = 8) -> 8 is single digit, stop


 */
public class FindingSumOfDigitsUntilSumBecomesSingleDigit {

    public static void main(String[] args) {
        int number = 108;
        System.out.println(findingSumOfDigitsUntilSingleDigitRecursive(number));
        System.out.println(findingSumOfDigitsUntilSingleDigitIterative(number));
        System.out.println(findingSumOfDigitsUntilSingleDigitOptimizedWay(number));
    }

    //Recursive Approach
    private static int findingSumOfDigitsUntilSingleDigitRecursive(int number) {
        if(number < 10){
            return number;
        }

        int count = 0;

        while(number != 0) {
            count += number % 10;
            number = number / 10;
        }

        if (count >= 10) {
            return findingSumOfDigitsUntilSingleDigitRecursive(count);
        }

        return count;
    }

    //Iterative Approach
    private static int findingSumOfDigitsUntilSingleDigitIterative(int number) {
        if(number < 10){
            return number;
        }

        int count = 0;

        while(number != 0) {
            count += number % 10;
            number = number / 10;

            if (number == 0 && count >= 10) {
                number = count;
                count = 0; //initialize count back to 0 for fresh counting;
            }
        }
        return count;
    }

    /*
    multiples of 9 has property that the digits of multiples of nine sum to nine.
    9 * 2 = 18 (1 + 8 = 9)
    9 * 3 = 27 (2 + 7 = 9)
    9 * 9 = 81 (8 + 1 = 9)
    9 * 12 = 108 (1 + 0 + 8 = 9) and so on

    -> so if you divide any number by 9 and if it is perfectly divisible by 9, then answer you will get is 9.
    Example:
            108 / 9 = perfectly divisible by 12, so sum of 108 will definitely be 9
            36 / 9  = perfectly divisible by 4, so sum of 36 will definitely be 9
            and so on.
    -> if the number is not perfectly divisible by 9, then return whatever is number mod 9.
       when you divide the number by 9, result(mod) will definitely be either 9 or less than that.

     */
    private static int findingSumOfDigitsUntilSingleDigitOptimizedWay(int number) {
        if (number == 0) {
            return 0;
        }
        if (number % 9 == 0) { //Check if number is perfectly divisible by 9
            return 9;
        } else {
            return number % 9;
        }
    }
}
Refer this video for best explanation on 
at

No comments:

Post a Comment