题目描述

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

样例

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

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

算法分析

$x = \overline {a_{n - 1}a_{n - 2}…a_{0}} = a_{n - 1} \cdot 10^{n-1} + a_{n - 2} \cdot 10^{n-2} + … + a_{0} \cdot 10^{0}$

$\quad$$\equiv a_{n - 1} \cdot 10^{n-1} mod 9 + a_{n - 2} \cdot 10^{n-2} mod 9 + … + a_{0} \cdot 10^{0} mod 9 \pmod 9$

$\because 10^x mod 9 = 1$

$\therefore x = \equiv a_{n - 1} + a_{n - 2} + … + a_{0} \pmod 9$

因此要求各位相加的结果，只需要对 $x$ 取 $mod 9$ 操作
$x mod 9$ 有两种情况

• 1、$1$ 到 $8$，各位相加对应是 $1$ 到 $8$
• 2、$0$
  • (1)当 $x = 0$ 时，各位相加是 $0$
  • (2)当 $x != 0$ 时， 各位相加是 $9$

时间复杂度 $O(1)$

Java 代码

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