258.各位相加

发表于 更新于 分类于 ，

题目

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

示例:

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

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

思路

这道题非常有意思的点是进阶里面说的:

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

说明这道题不止只有暴力循环解法,还有更巧妙的,只用O(1)时间的解法,也就是说,连扫描一趟的功夫都不用,直接就能得到结果.

这个时候就应该通过数学找规律来解题了,先用比较小的数去尝试看看能不能发现规律:

10---1

11---2

12---3

18---9

19---1

20---2

21---3

99---9

100---1

101---2

102---3

109---1

110---2

111---3

117---9

可以看到,有某个数是比较特别的,那就是这个9.

各位相加答案为9的数,刚好也即是9的倍数.也就是说某个数能被9整除,那他的各位相加结果就刚好是9.

并且无法被9整除的数,得到的余数也就刚好是答案.

代码

暴力法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int AddDigits(int num)
{
    if (num < 10)
    {
        return num;
    }
    int result = 0;
    while (num >= 10)
    {
        result = 0;
        while (num != 0)
        {
            result += num % 10;
            num /= 10;
        }
        num = result;
    }
    return num;
}

规律法:

1
2
3
4
5
6
7
8
9
10
11
12
public int AddDigits(int num)
{
    if (num > 9)
    {
        num = num % 9;
        if (num == 0)
        {
            return 9;
        }
    }
    return num;
}