Add Digits

Problem

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.

Solution

My Original brute force solution

public class Solution {
    public int addDigits(int num) {
        while (num > 9) {
            String s = num + "";
            num = 0;
            for (char c : s.toCharArray()) num += Character.getNumericValue(c);
        }
        return num;
    }
}

Math solution with O(1) time and space

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

Analysis

The first brute force solution is pretty straightforward
We add each digit of num until it become less than 9
Notice that we convert char to int by Character.getNumericValue()

The Second solution is about Math and time complexity is O(1)
Take num = 12345 as an example
num = 1 * 10000 + 2 * 1000 + 3 * 100 + 4 * 10 + 5 * 1
1 * 10000 % 9 = 1
2 * 1000 % 9 = 2
...
num % 9 = (1 + 2 + 3 + 4 + 5) % 9 = 15 % 9 = (1 + 5) % 9 = 6 which is exactly what we want
Math is amazing