ReZero's Utopia.

Add Digits

字数统计: 228阅读时长: 1 min
2019/08/08 Share

Since 10^{i}$ \equiv 1(mod 9) ,then =>
(a_{i}$ * 10^{i}$ + a_{i-1}$ * 10^{i-1}$ + …) mod 9 = (a_{i}$ * 10^{i}$ mod 9 + a_{i-1}$ * 10^{i-1}$ mod 9 + …) mod 9
= (a_{i}$ + a_{i-1}$ + …) mod 9

https://leetcode.com/problems/add-digits/discuss/68580/Accepted-C%2B%2B-O(1)-time-O(1)-space-1-Line-Solution-with-Detail-Explanations

https://en.wikipedia.org/wiki/Digital_root#Congruence_formula

For base b (decimal case b = 10), the digit root of an integer is:

  • dr(n) = 0 if n == 0
  • dr(n) = (b-1) if n != 0 and n % (b-1) == 0
  • dr(n) = n mod (b-1) if n % (b-1) != 0

or

  • dr(n) = 1 + (n - 1) % 9

Note here, when n = 0, since (n - 1) % 9 = -1, the return value is zero (correct).

From the formula, we can find that the result of this problem is immanently periodic, with period (b-1).

Output sequence for decimals (b = 10):

1
2
~input: 0 1 2 3 4 ...
output: 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 ....

Henceforth, we can write the following code, whose time and space complexities are both O(1).

1
2
3
4
5
6
class Solution {
public:
int addDigits(int num) {
return 1 + (num - 1) % 9;
}
};
CATALOG