258: 各位相加
题目描述
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
Example:
Input: 38
Output: 2
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
Follow up: Could you do it without any loop/recursion in O(1) runtime?
解题思路
数根的定义
这个题目其实是让求一个非负整数的数根，关于数根的定义如下:
在数学中，数根（又称位数根或数字根 Digital root）是自然数的一种性质，
数根是将一正整数的各个位数相加（即横向相加），若加完后的值大于10的话，则继续将各位数进行横向相加直到其值小于10为止。
或是，将一数字重复做数字和，直到其值小于10为止，则所得的值为该数的数根。
例如54817的数根为7，因为5+4+8+1+7=25，25大于10则再加一次，2+5=7，7小于十，则7为54817的数根。
自然数和它的数根模9同余
要求一个数的数根，我们需要了解数根的一个重要性质:
自然数
N和它的数根X，对9取余，他们的余数相同
接下来我们证明一下这个性质，
假设有一个n位的10进制自然数N，我们可以写成
因为
- \( 10^n \equiv 1^n \equiv 1 \pmod 9 \)，即 \(10^n\) ， \(1^n\) 和 1 模9，得到的余数都是1。
- 模运算的乘法运算规则
所以
\( \sum_{i=0}^{n} a_i \) 即是自然数N的各个位数相加，我们将自然数N的各个位数相加的操作称为f，其相加结果为f(N)
可得 \( N \equiv f(N) \pmod 9\)
进一步可得 \( N \equiv f(N) \equiv f(f(N)) \equiv f(f(f(N))) \pmod 9 … \)
N的数根是重复各个位数相加的过程得来的，所以可得 \( N \equiv N的数根 \pmod 9 \)
代码
根据自然数和它的数根模9同余的性质，我们可以推断出，一个数的数根是它模9的余数，或者是9（模9等于0）。
最终代码如下:
package l258
// addDigits 计算 __数根__ 的程序
func addDigits(num int) int {
if num <= 0 {
// 非自然数及0的情况
return 0
} else {
res := num % 9
if res == 0 {
// 模9等于0时，其数根为9
return 9
} else {
// 自然数的数根为其模9的余数
return res
}
}
}
- 测试代码
package l258
import (
"testing"
"github.com/stretchr/testify/assert"
)
func TestAddDigits(t *testing.T) {
assert.Equal(t, 2, addDigits(38))
assert.Equal(t, 0, addDigits(0))
assert.Equal(t, 9, addDigits(9))
assert.Equal(t, 9, addDigits(18))
}