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 };

Leetcode 258. Add Digits