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

Straightforward solution of this problem is to do exactly what is asked, until we get only one digit. However, there is smarter mathematical solution, using property of division by 9. Let us condiser first example and then formulate result for general case:

Let n = 18102. Then numbers n and sum(n) (where by sum(n) we denote sum of digits of number n) have the same remainder if we divide them by 9. Why so? To prove, that two numbers have the same remainder is equivalent to prove, that difference of these two numbers is divisible by 9. Indeed: 18102 - sum(18102) =10000 + 8*1000 + 1*100 + 0*10 + 2 - (1 + 8 + 1 + 0 + 2) = 9999 + 8*999 + 1*99 + 0*9 + 0 is divisible by 9, because each term is divisible by 9. So, now, we can state theorem:

Theorem For any natural number n: numbers n and sum(n) have the same remainder if we divide them by 9. Proof: let n = a_n ... a_2 a_1 a_0, then n - sum(n) = a_n* 99...9 + ... + a_2 * 99 + a_1*9 + 0, which is divisible by 9.

Now, let us go back to our problem: we evaluate sum of digits of our number several times, until we reached 1-digit number. On each iteration remainder of divition by 9 is the same. So in the very end it also be the same! So, what we need to do is just return this reminder? Almost, there are two cases we need to hanlde:

  1. If n = 0, then we return 0.
  2. If n > 1 and n is divisible by 9, then reminder is equal to 0. However we can not reach 0, and the answer will be another digit with reminder equal to 0, which is 9.

Complexity: time and space complexity is O(1).

Finally, it can be written as oneliner:

class Solution:
    def addDigits(self, num):
        return 0 if num == 0 else (num - 1) % 9 + 1

If you like the solution, you can upvote it on leetcode discussion section: Problem 0258