Problem

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

Examples

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.

Solution

Method 1 - Recursion

Code

Java
public int addDigits(int num) {
	int sum = 0;

	String s = String.valueOf(num);

	for (int i = 0; i < s.length(); i++) {
		sum = sum + (s.charAt(i) - '0');
	}

	if (sum < 10) {
		return sum;
	} else {
		return addDigits(sum);
	}
}

Method 2 - Math

The problem, widely known as digit root problem, has a congruence formula. Lets look at a key observation:

0 - 9 is easy. But now look at 10 -18 - the number and their sum:

10 1
11 2
12 3
13 4
14 5
15 6
16 7
17 8
18 9

Similarly, lets look at numbers in 19 - 27 and their sum:

19 1
20 2
21 3
22 4
23 5
24 6
25 7
26 8
27 9

So, notice that sum of digits revolves between 1 and 9. And the value is num % 9 when num is not divisibly by 9, otherwise it is 9.

int addDigits(int num) {
	if ( num == 0 ) return 0;
	return num%9 == 0 ? 9 : num%9 ;
}

We can actually get rid of if condition, and make it one liner with this trick:

  • We find the modulo 9 of the previous number and add one to it
int addDigits(int num) {
	return 1 + (num - 1) % 9;
}

Code

Java
With if condition
int addDigits(int num) {
	if ( num == 0 ) return 0;
	return num%9 == 0 ? 9 : num%9 ;
}
Without if condition
int addDigits(int num) {
	return 1 + (num - 1) % 9;
}