[leetcode] 258. Add Digits

[leetcode] 258. Add Digits

Description

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. Since 2 has only one digit, return it.

Follow up: Could you do it without any loop/recursion in O(1) runtime?

分析

如果是常量时间复杂度的话，最先想到的是有没有什么捷径，所以 我们先来观察1到20的所有的数根： 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 1 20 2根据上面的列举，我们可以得出规律，每9个一循环，所有大于9的数的树根都是对9取余，那么对于等于9的数对9取余就是0了，为了得到其本身，而且同样也要对大于9的数适用，我们就用(n-1)%9+1这个表达式来包括所有的情况。看来数学功底好也很重要的

代码

class Solution {public: int addDigits(int num) { return (num-1)%9+1; }};

参考文献

​​[LeetCode] Add Digits 加数字​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。