【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來移除個位數。
• 進階可以參考這篇和這裡。
• 裡面提到在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++