258

258. Add Digits (Easy)

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

 

Example 1:

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

Example 2:

Input: num = 0
Output: 0

 

Constraints:

• 0 <= num <= 231 - 1

 

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

Companies:
Amazon

Related Topics:
Math, Simulation, Number Theory

Similar Questions:

• Happy Number (Easy)
• Sum of Digits in the Minimum Number (Easy)
• Sum of Digits of String After Convert (Easy)
• Minimum Sum of Four Digit Number After Splitting Digits (Easy)

Solution 1.

The value we're asked to compute is the so-called Digital Root.

// OJ: https://leetcode.com/problems/add-digits/
// Author: github.com/lzl124631x
// Time: O(lgN)
// Space: O(1)
class Solution {
public:
    int addDigits(int n) {
        while (n > 9) {
            int next = 0;
            for (; n; n /= 10) next += n % 10;
            n = next;
        }
        return n;
    }
};

Solution 2.

See explanation in https://leetcode.com/problems/add-digits/solution/.

// OJ: https://leetcode.com/problems/add-digits/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
    int addDigits(int num) {
        return num ? (num % 9 ? num % 9 : 9) : 0;
    }
};

Or

// OJ: https://leetcode.com/problems/add-digits/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
    int addDigits(int num) {
        return num ? 1 + (num - 1) % 9 : 0;
    }
};