【LeetCode】258.Add Digits

LeetCode-258

Links：https://leetcode.com/problems/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?

 

思路：整数(abcde) = a+b+c+d+e+(a*9999+b*999+c*99+d*9);

我们可以知道，

(a*10000+b*1000+c*100+d*10+e)%9

=( (a+b+c+d+e)%9 +  (a*9999+b*999+c*99+d*9)%9 ) %9

= (a+b+c+d+e) %9

假设整数(x*10+y) = a+b+c+d+e （只可能是两位数…）可以知道：

(xy) % 9 =  (x+y)%9

18%9 = 0

……

依次类推可以得到：

整数%9的值即为它的各个位数相加的值.

特例：9的倍数：9 ， 18 ，27….

所以可以得到以下公式： (num-1)%9+1;