Today’s Leetcode July Challenge involves the application of a simple mathematical property. The problem, Add Digits, gives us a non-negative integer and asks us to sum the digits until we’re left with a single digit number, and return it. Without any mathematical knowledge, we can write a pretty good O(n) algorithm. Note: n here is actually a mathematical property called additive persistence that describes the number of iterations required to transform an integer to its digital root.

int addDigits(int num) {
   while(num > 9) {
	  int temp = 0;
	  while(num > 0) {
		 temp += num % 10;
		 num /= 10;
	  }
	  num = temp;
   }
   return num;
}

The problem also offers the challenge to write a O(1) algorithm, but in order to do so we need to know or discover the periodic property of digital roots and derive the congruence formula. We’ll just take Wolfram’s word for it. $$ dr(n) = [(n-1) \bmod 9] + 1, \; \textrm{where} \; n \gt 0 $$

That’s it. We’ll just put that in an algorithm and run with it. This is really a case of either knowing the formula or not, but this was a great opportunity to learn it or be refreshed on it and it’s a pretty neat reduction operation to have in your mind.

int addDigits(int num) {
   if(num) {
	  num = ((num-1) % 9) + 1;
   }
   return num;
}