1.题目

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

示例：

  1. 输入: 38
  2. 输出: 2 
  3. 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

进阶：

你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？

2.思路

很明显我们可以做除10取整、取余的操作，和各位相乘类似

  1.     public int addDigits(int num) {
  2.         int sum = 0;
  3.         while (num != 0){
  4.             sum += num % 10;
  5.             num /= 10;
  6.         }
  7.         if (sum >= 10){
  8.             return addDigits(sum);
  9.         }else {
  10.             return sum;
  11.         }
  12.     }

我也只会这样求，但是官方说要不使用循环或者递归，且在O(1)时间复杂度内完成，这里就引申出一个数学问题，那就是求数根

这里列一个公式出来：a的数根b = (a-1) % 9+1, 即 mod(a-1, 9)+1，且a ∈ N*（其实有了公式，程序也就出来了~）

那么我们列举一下部分数字的树根

  1. 原数:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
  2. 数根:1 2 3 4 5 6 7 8 9  1  2  3  4  5  6  7  8  9  1  2  3  4  5  6  7  8  9  1  2  3

这里我们拿28、29举例子，按照题目要求求得的最终结果分别是1、2，我们可以发现其实与它的数根一样，那么我们的程序只要把公式带入就好了

  1.     public int addDigits(int num) {
  2.         return (num - 1) % 9 + 1;
  3.     }