Leetcode[258]. Add Digits
文章目录
题目描述
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
,我们可以写成 $ N = \sum_{i=0}^{n} a_i * 10^i $
因为
- $ 10^n \equiv 1^n \equiv 1 \pmod 9 $,即 $10^n$ , $1^n$ 和 1 模9,得到的余数都是1。
- 模运算的乘法运算规则 $ (a * b) % p \equiv (a % p * b % p) % p $
所以 $ N \equiv \sum_{i=0}^{n} a_i \pmod 9 $,
$ \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)。
最终代码如下:
|
|
- 测试代码
|
|