# 258. Add Digits

• ## Solution

### Approach #1 Traditional Way Using Loops or Recursion

Using loops or recursion to calculate the sum of digits until it less than 10

``````public class Solution { // using recursion
public int addDigits(int num) {
if(num < 10) return num;
int re = 0;
while(num > 0){
re += num % 10;
num /= 10;
}
return addDigits(re);
}
}
``````

### Approach #2 Find The Pattern

Since there are only 10 possible results ( 0 ~ 9 ) and only addDigits(0) = 0 , we can analysis the pattern as below

``````for input n :
addDigits(0) = 0;
if addDigits(n) + 1 < 10
addDigits(n+1) = addDigits(n) + 1
else
addDigits(n+1) = addDigits( addDigits(n) + 1 )
if addDigits(n) == 9
addDigits(n + 1) = addDigits( 10 ) = 1

``````

From the above we can see the answer repeated from 1 ~ 9 since the input > 0, we can get than

``````     addDigits(n) = addDigits(n-9) ;  // n - 9 > 0
``````

Only we need is try to reduce the input to 1 ~ 9 and that's the answer.

``````public class Solution { // using recursion
public int addDigits(int num) {
return 1 + (num - 1) % 9;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.