# 【LeetCode】 258. Add Digits

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

> Follow up:
Could you do it without any loop/recursion in O(1) runtime?

> 給一個非負整數`num`，重複地把它所有位數加總，直到結果只剩個位數。

> 進階題：
> 你可以不使用任何迴圈/遞迴且在O(1)的時間複雜度完成嗎？

## Example:

Input: 38
Output: 2 
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2. 
             Since 2 has only one digit, return it.

## Solution

* 用`%10`取出個位數，用`/10`來移除個位數。
* 進階可以參考[這篇](https://en.wikipedia.org/wiki/Digital_root)和[這裡](https://oeis.org/A010888)。
* 裡面提到在base為10(十進位)之下，數根將會與九的模數有關，詳細證明就請自行翻閱上面參考資料。

### Code

class Solution {
public:
    int addDigits(int num) {
        while(num > 9)
        {
            int temp = 0;
            while(num != 0)
            {
                temp += num % 10;
                num /= 10;
            }
            num += temp;
        }
        return num;
    }
};

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

###### tags: `LeetCode` `C++`