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:
Example:
Find the digital root of 257520643
Steps:
- 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