258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. 

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

Solution:

Let's list a bunch of numbers and the results:

0    0
1    1
2    2
3    3
4    4
5    5
6    6
7    7
8    8
9    9
10  1
11  2
12  3
13  4
14  5
15  6
16  7
17  8
18  9
19  1
20  2
21  3
22  4
...   ...

The results are looping from 1 to 9, except the first 0.

So the rules can be:

1. If the number is 0, the result is 0.

2. If the number mod 9 is 0, the result is 9.

3. Otherwise, the result is number mod 9.

Actually, this is called Congruence formula: (n - 1) % 9 + 1



Code:

public class Solution {
    public int addDigits(int num) {
        return (n - 1) % 9 + 1;
    }
}