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?

Hint:

A naive implementation of the above process is trivial. Could you come up with other methods?
What are all the possible results?
How do they occur, periodically or randomly?
You may find this Wikipedia article useful.

分析

题目要求一个数的数字根，一开始我的想法是像题目说的一样，一直循环/递归去找到答案，但是感觉好麻烦，看了提示后，百度了一下数字根后，原来有这么一个公式可以快速求

a的数根b = ( a - 1) % 9 + 1

原来如此简单，但是为什么会这样子呢？想不明白，后来查了下资料，感觉这个解释好像有点道理

12,345 = 1 × (9,999 + 1) + 2 × (999 + 1) + 3 × (99 + 1) + 4 × (9 + 1)+ 5.
12,345 = (1 × 9,999 + 2 × 999 + 3 × 99 + 4 × 9) + (1 + 2 + 3 + 4 + 5).

所以数根就是这个数对9的余数，但是当这个数为9的时候就不行了，所以先减去1再加上1(可以这样子做吗？好像可以吧。)

代码

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