23
Digital Root of a given number
Algorithm
C
C++
Java
Python

What is Digital root?

If we add up the digits of a number until there is only one number left we have found what is called the digital root. In other words, the sum of the digits of a number is called its digital root.

      Example:

      For 5674, 5 + 6 + 7 + 4 = 22 and 2 + 2 = 4

      » 4 is the digital root of 5674

One use of digital roots is for divisibility tests (like 3 and 9). This method makes it easier to calculate the digital root.

Example:Digital Root

Example:

      Find the digital root of 257520643

Digital Root

Steps:

  1. 2 + 7 = 9, cross out 2 and 7.

2.4 + 3 = 9, cross out 4, 3 and 2.

3.There are no other groups of numbers adding up to 9.

4.Add up the remaining digits, 5 + 5 + 0 + 3 = 13.

5.13 is more than 9, so 1 + 3 = 4.

6.The digital root is 4.

If there is nothing left after having cast out nines then the digital root is 9.

Efficient Implementation Code

    int digitalRoot(char num[]){
    int len = strlen(num);
    int ans= 0;
    for(int i=0;i<len;i++){
        ans = 1 + ( ans + (num[i] - '0') - 1 ) % 9;
    }
    return ans;
}

Simple         Efficient
------         ---------
34758          1+(3-1)%9   = 3
3+4+7+5+8      1+(3+4-1)%9 = 7
7+7+5+8        1+(7+7-1)%9 = 5
14+5+8         1+(5+5-1)%9 = 1
1+4+5+8        1+(1+8-1)%9 = 9
5+5+8          9
10+8
1+0+8
1+8
9

Edit: One Liner Solution

return num == 0 ? 0 : ( num % 9 == 0 ? 9 : ( num % 9 ));

Reference : http://esolangs.org/wiki/Digital_root_calculator#Efficient_calculation

Author

?