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:
考虑 O(1) 的算法，从最朴素的数字开始：
0 - 9 无疑都对应返回 0 - 9 就行了。
接下来，
10 返回 1
11 返回 2
12 返回 3
13 返回 4
……
18 返回 9
19 返回 1
……
规律呼之欲出，因为最终所有的数字都将被 映射到 0 - 9 这 10 个数字上，所以才开始考虑这样的映射是否存在一些本质上的规律，那么由上述可以发现规律就是随着数字本身的大小递增，最后映射到的数其实也是递增的，但这样的递增其实是以 9 为模，而对于此题我们最后只关心取模后的余数而不关心数字本身有几个“模9”了。
需要注意的一点是：
0 在这里是特殊的，只有 0 数字本身映射到 0 ，再也没有其他数字映射到 0，需要单独处理。
所以实际上 我们是将 除0外的数字 映射 到 1-9 这九个数字上，想想便知结果应该是 (num-1) % 9 + 1。
代码如下：
class Solution:
# @param {integer} num
# @return {integer}
def addDigits(self, num):
if num == 0:
return 0
else:
return (num-1) % 9 + 1