AddDigitsOPT [source code]

public class AddDigitsOPT {
    public int addDigits(int num) {
        return num % 9 == 0 ? (num == 0 ? 0 : 9) : num % 9;
    }
}

submission 最优解, 1ms;

好像是利用数学上的一个什么性质:
https://en.wikipedia.org/wiki/Digital_root#Congruence_formula

这个是另外一个类似的版本:

public class Solution {  
    public int addDigits(int num) {  
        return 1 + (num - 1) % 9;  
    }  
}

lc 的 discussion 给出了其他很多不同的解释:

Hi, if you list all results from 0 to 30, you may see some rule. the results periodically occur.

0~9 (10 nums) : 0,1,2,3,4,5,6,7,8,9
10~18(9 nums): 1,2,3,4,5,6,7,8,9
19~27(9 nums): 1,2,3,4,5,6,7,8,9
and so on
only need to be careful about 0 and the multiples of 9.
Hope it helps!

这个人的意思就是直接当做 pattern 题来做了, 也无可厚非;

I think like this:

num = 10 a + b = a + b + 9 a
when you add all digits, the result is sum = num - 9*a, make sum the smallest,
while sum > 0, when you get the new sum

If sum > 10, do sum1 = sum - 9a1 again
else sum is the result
so we can get the answer, result = num - num / 9 9

Only thing you have to do is:

when num == 0, ok the result is right
when num%9 == 0', oops, the result is 0, but the real result isresult > 0`, so it is 9.

这个是另外一个人的思路, 可以大概帮助理解9是怎么来的. 不过整体的证明思路感觉还是不是很完整, num = 10 * a + b
这个表达对于三位及以上就不是特别适用了;

I'll try to explain the math behind this:

First you should understand:

10^k % 9 = 1
a*10^k % 9 = a % 9
Then let's use an example to help explain.

Say a number x = 23456

x = 2 10000 + 3 1000 + 4 100 + 5 10 + 6

2 * 10000 % 9 = 2 % 9

3 * 1000 % 9 = 3 % 9

4 * 100 % 9 = 4 % 9

5 * 10 % 9 = 5 % 9

Then x % 9 = ( 2+ 3 + 4 + 5 + 6) % 9, note that x = 2 10000 + 3 1000 + 4 100 + 5 10 + 6

So we have 23456 % 9 = (2 + 3 + 4 + 5 + 6) % 9

这个是一个很聪明的解释, 解释了为什么只要对最开始的 num 进行一次 mod9就行了;

这个题大概就看这么多吧, 以后有时间再看这些不够 general 的题目;

Problem Description

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, 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?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

Difficulty:Easy
Category:Algorithms
Acceptance:50.93%
Contributor: LeetCode
Topics:
Math
You might like:
(E) Happy Number
Company:
Adobe Microsoft