Add Digits

Problem

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

Example

Given num = 38. The process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return 2.

Solution

A math trick: the sum of digits mod 9 is the same as the number mod 9. For example:

  • 38 % 9 = 2, (3 + 8) % 9 = 11 % 9 = 2
  • 111 % 9 = 3, (1 + 1 + 1) % 9 = 3
  • 18 % 9 = 0, (1 + 8) % 9 = 0

However there's one exception in this problem: 9 % 9 = 0 but 9 is a single digit so should return 9 instead of 0. To handel this, we can either

return num % 9  == 0  ? 9 : num % 9

or

return 1 + (num - 1) % 9

Code - Java

public class Solution {
    /**
     * @param num a non-negative integer
     * @return one digit
     */
    public int addDigits(int num) {
        // Write your code here
        return 1 + (num - 1) % 9;
    }
}