Leetcode - Add Digits (Math Explained)

July 2020 Leetcode Challenge
Original Question : • Leetcode - Add Digits ...
Trying to explain the math.. I don't really understand it myself so any help would be appreciated!

[@Laxplayer14033]

Here is an explanation I came up with based on my learning that helped me in case you or anyone is interested still: Any number where it's digits add to 9 is always divisible by 9. (18, 27, 36, 45, 54, 63, 72, 81, 90, etc.) Therefore the 'digital root' for any number divisible by 9 is always 9. You can see this even in larger numbers like 99 because 9 + 9 = 18, and then 1 + 8 = 9 still, so the root always becomes 9 for any numbers divisible by 9. Additionally, 0 always has a digital root of 0 obviously. The only other cases you need to worry about to find the digital root are when it isn't 0 or 9. So for any number that isn't 0 and isn't divisible by 9, the root will always n % 9 for a given number n. (AKA the difference between given number n and the nearest number that is divisible by 9, since numbers divisible by 9 always have a digital root of 9). For examples: 100 % 9 = 1 (one greater than 99, which is divisible by 9). 101 % 9 = 2 102 % 9 = 3 and so on. This explanation/algorithm skips the whole "add digits until there is only 1 remaining", so the description of this problem seems pretty misleading to me since it makes you think the solution will be something unrelated to the optimal one. I guess the point of Leetcode is to learn all of these tricks though. @Jan Michael Austria's solution is essentially this with the non-zero cases combined into one return statement with a bunch of math. Hope this helps someone out there and wasn't too confusing!

[@timc3406]

Thanks for the great explanation there! This is really high level stuff!

[@Laxplayer14033]

@@timc3406 Much appreciated!

[@Sapphiamur]

What an awesome explanation, thanks a lot! :))

[@janmichaelaustria620]

Math!! Nice! The floor function from the wiki article makes a little more sense to me, and you can adjust it for any base class Solution(object): def addDigits(self, num,base): if num == 0: return 0 return num - (base-1)*((num-1)//(base-1))

[@timc3406]

I still have trouble understanding the math behind it but I guess as long as we get the gist, it's fine

[@nicklandreth2527]

You said there are better explanations. What would I look up to find an explanation of the mathematical rule here?

[@timc3406]

The solution should be up there on leetcode, you can take a look here leetcode.com/problems/add-digits/solution/