leetcode #256 add digits (difficulty: easy)

问题 : >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?

原题链接

这个问题，需要用到这一篇维基百科文章。

C++ :

1
2
3
4
5
6
7
8

class Solution {
public:
    int addDigits(int num) {
        if(num == 0) return 0;
        if(num%9 == 0) return 9;
        return num%9;
    }
};

这道题的就是求 Digit Root （这里简称 DR ）。求 DR 有公式可以求，其利用的技巧是10的幂数对9求余结果总是1。以上的求 DR 过程就可以看成是分部对9求余的过程。这一性质可以用以下的公式描述。

displaystyle
text{dr}(abc) = acdot10^2+bcdot10+ccdot1=a+b+c

求DR的公式：

displaystyle
text{dr}(n) =
begin{cases}
0,&text{if$n=0$,} \
9,&text{if$nneq0,n%9=0$,} \
n%9,&text{if$n%9neq0$.}
end{cases}