[容易]569.各位相加

我是小小强，这是我的第7篇原创文章，阅读需要大约10分钟。

---

题目

LintCode:各位相加

描述

给出一个非负整数 num，反复的将所有位上的数字相加，直到得到一个一位的整数。

样例

给出 num = 38。
相加的过程如下：3 + 8 = 11，1 + 1 = 2。因为 2 只剩下一个数字，所以返回2。

思路

题目要求各位相加，想当然的思路就是每次除于10，然后余数相加，直到无法被10整除，然后再把最后的余数加起来。

实现

递归实现

1. java实现

   public class Solution {
       /**
        * @param num a non-negative integer
        * @return one digit
        */
       public int addDigits(int num) {
           // Write your code here
           int sum = 0;
           while(num / 10 >= 1){
               sum += num % 10;
               num /= 10;
           }
           sum += num % 10;
           if (sum >= 10)
               sum = addDigits(sum);
           return sum;
       }
   }

2. 结果分析
   结果：结果通过了LintCode的要求。
   分析：这种实现比较好理解，但是实现起来却没什么巧妙之处。并且时间慢。

其它优化参考

LintCode:569 各位相加
LeetCode discuss

数学原理

https://en.wikipedia.org/wiki/Digital_root
[Step 1]:

438  == 40*10 +3*10 +8 ;
4+3+8 == 4*(10%9)*(10%9)+3*(10%9)+8%9= 15   ;

[Step 2]:

15  == 1*10 + 5 ; 
1+5 == 1*(10%9)+5%9= 6 ;

[So we can see]:

ab%9%9%9==ab%9; 
just return num%9; and don't forget num==0 or num==9

优秀代码

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