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?

My solution

肯定是很搓的while咯...

class Solution {public:    int addDigits(int num) {        int sum=0;        int shang;        int yu;        while(true){            yu=num%10;            num/=10;            sum+=yu;            if(num==0){                if(sum<10) break;                else{                    num=sum;                    sum=0;                }            }        }        return sum;    }};

Discuss

果然有固定算法

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

主要理解下面式子:

$${\mbox{dr}}(abc)\equiv a\cdot 10^{2}+b\cdot 10+c\cdot 1\equiv a\cdot 1+b\cdot 1+c\cdot 1\equiv a+b+c{\pmod {9}}.$$

把一个数(如438)拆解:

400->40->4 30->38因为10->1是mod 9, 100->1也是100=1+99也通过mod 9实现,具体原因脑子有点绕.

比较trick的方案不那么容易想到, 快速看答案就行...

Reference