[leetcode #258] Add Digits

## Problem

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 <= 2³¹ - 1

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

Idea

Brute-force로 풀어도 쉽게 풀 수 있는 문제다. 주어진 수를 10으로 계속해서 나누면서 더하고, 더한 값이 10보다 작을 때까지 과정을 반복한다.

하지만 수학적 원리를 이용하면 더 간단하게 풀 수 있다. 바로 "어떤 수는 각 자리 수를 전부 더한 값이 9로 나뉠 때만 9로 나뉘어질 수 있다."라는 원리다. 이 원리를 이용하면 원하는 값을 digital root라고 할 때 다음과 같은 결과가 도출된다.

dr(n) = 0, if n = 0

dr(n) = 9, if n = 9k

dr(n) = n mod 9, if n != 9k

(자세한 건 풀이 참조 → https://leetcode.com/problems/add-digits/solution/)

Solution

class Solution {
    public int addDigits(int num) {
        do {
            String str = Integer.toString(num);
            num = 0;
            for (int i=0; i < str.length(); i++) {
                num += str.charAt(i) - '0';
            }
        } while (num >= 10);

        return num;
    }
}

class Solution {
    public int addDigits(int num) {
        if (num == 0) return 0;
        if (num % 9 == 0) return 9;
        return num % 9;
    }
}

Reference

https://leetcode.com/problems/add-digits/