LeetCode 258 Add Digits（数字相加，数字根）

翻译

给定一个非负整型数字，反复相加其全部的数字直到最后的结果仅仅有一位数。

比如：

给定sum = 38，这个过程就像是：3 + 8 = 11。1 + 1 = 2。由于2仅仅有一位数。所以返回它。

紧接着：

你能够不用循环或递归在O(1)时间内完毕它吗？

原文

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?

分析

事实上我并不会写，循环和递归都不能用……我还能怎么办呐。文章来源地址https://www.yii666.com/article/764053.html

然后看了LeetCode上给的提示。看了维基百科的一篇文章：Digital root。文章地址https://www.yii666.com/article/764053.html

网址:yii666.com<网址:yii666.com文章来源地址:https://www.yii666.com/article/764053.html

有了这个的话，就非常easy了。详细这个公式的细节，大家自己參看维基吧，由于篇幅过长就不翻译了。

代码

class Solution {

public:

    int floor(int x) {

        return (x - 1) / 9;

    }

    int addDigits(int num) {

        return num - 9 * floor(num);

    }

};