Leetcode 258. Add Digits

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?

题目大意：

给定一个非负整数num，重复地将其每位数字相加，直到结果只有一位数为止。

例如：

给定 num = 38，过程像这样：3 + 8 = 11, 1 + 1 = 2。因为2只有一位，返回之。

进一步思考：

你可以不用循环，在O(1)运行时间内完成题目吗？

提示：

一个直观的解法就是模拟上述过程。你可以想到别的方法吗？

结果一共有多少种可能性？

它们是周期性出现的还是随机出现的？

解题思路：

方法I：按照题目要求使用循环模拟演算过程

 1 int addDigits(int num) {
 2         while(num > 9){
 3             int c = 0;
 4             while(num > 0){
 5                 c += num % 10;
 6                 num /= 10;
 7             }
 8             num = c;
 9         }
10         return num;
11     }

方法二：假如一个数9856 % 9 = （9 * 1000 + 8 * 100 + 5 * 10 + 6） % 9 = （9 * 1000 % 9 + 8 * 100 % 9 + 5 * 10 % 9 + 6 % 9 ) % 9 =( 9 + 8 + 5 + 6) % 9 = 28 % 9 = 1

如果n != 0 且每一位加起来的和是9的倍数，那么则输出9，否则输出 n % 9;

1 class Solution {
2 public:
3     int addDigits(int num) {
4         if(num != 0 && (num % 9) == 0)
5             return 9;
6         return num % 9;
7     }
8 };