Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
Example:
Input:38Output: 2 Explanation: The process is like:3 + 8 = 11,1 + 1 = 2. Since2has only one digit, return it.
Follow up:
Could you do it without any loop/recursion in O(1) runtime?
Solution 1: Simulation
Time complexity: O(logn)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: int addDigits(int num) { int n = num; while (n >= 10) { int t = n; n = 0; while (t) { n += t % 10; t /= 10; } } return n; } }; |
Solution 2: Math
https://en.wikipedia.org/wiki/Digital_root#Congruence_formula
Digit root = num % 9 if num % 9 != 0 else min(num, 9) e.g. 0 or 9
Time complexity: O(1)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 |
// Author: Huahua class Solution { public: int addDigits(int num) { return num % 9 ? num % 9 : min(num, 9); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment