README.md

各位相加

难度：简单

https://leetcode-cn.com/problems/add-digits/

题目

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

示例 1:

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

示例 2:

输入: num = 0
输出: 0

解题

模拟

/**
 * 模拟
 * @desc 时间复杂度 O(logN)  空间复杂度 O(1)
 * @param num
 */
export function addDigits(num: number): number {
  while (num >= 10) {
    let sum = 0;
    while (num) {
      sum += num % 10 >> 0;
      num /= 10;
    }
    num = sum;
  }

  return num;
}

数学

假设有一个n位的 10 进制数，我们写成 ，其中ai表示从低到高的每一位。

因为

a ≡ b mod c：指的是 a，b 对于模 c 同余，即a%c === b%c

那么

即

也就是一个数和它的各数位之和的模 9 相同。

因此我们可以设

即

所以可以推出

现在我们回归到题目，题目想要我们求出num的树根，也就是反复将各个位上的数字相加 ，直到结果为一位数。这个结果也成为num的树根。

首先我们需要将每一位进行累加，即f(x)，然后当它还大于 9 的话，继续递归调用， 即f(f(x))。

因此综上我们可得出，num的树根与num的模 9 相同。

然而树根的区间为[0,9],我们可以通过下面例子看一下。

原数	0	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
数根	0	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
求余	0	1	2	3	4	5	6	7	8	0	1	2	3	4	5	6	7	8	0	1	2	3	4	5	6	7	8	0	1	2	3

我们可以对树根分为以下三种情况：

• num是 0 的话，则树根为0。
• num是 9 的倍数的话，则树根为9
• num既不是 0 也不是 9 的倍数的话，则树根为num mod 9

因为我们可以考虑先让num向左偏移一位，然后求完余数后再补 1，因此求得树根。

原数	0	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
偏移	-1	0	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
求余	-1	0	1	2	3	4	5	6	7	8	0	1	2	3	4	5	6	7	8	0	1	2	3	4	5	6	7	8	0	1	2
余数加 1	0	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
树根	0	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

/**
 * 数学
 * @desc 时间复杂度 O(1)  空间复杂度 O(1)
 * @param num
 */
export function addDigits2(num: number): number {
  return ((num - 1) % 9) + 1;
}