258. Add Digits

青旅半醒 2022-07-15 01:27 177阅读 0赞

Given a non-negative integer `num`, repeatedly add all its digits until the result has only one digit.

For example:

Given `num = 38`, 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?

Hint:

1.  A naive implementation of the above process is trivial. Could you come up with other methods?
2.  What are all the possible results?
3.  How do they occur, periodically or randomly?
4.  You may find this [Wikipedia article][] useful.

解析：

假设输入的为四位数num，且其位数从高到低以此为a、b、c、d，那么num = a\*1000+b\*100+c\*10+d = a+b+c+d + a\*999+b\*99+c\*9+d\*0,由于（x+y）%z = （x%z+y%z）%z，那么num%9 = （（a+b+c+d）%9+0）%9 = （a+b+c+d）%9，假设a+b+c+d = num1，那么num1由可以按上述方式继续分解为num1 = a1+b1 + a1\*9+b1\*0，num1%9 = (a1+b1)%9，那么乍看起来，这么执行下去的结果就是给定值num各位数字相加得到的最后结果，但num%9的结果位于\[0,8\]之间，我们期望得到的值应该在\[1,9\]之间，所以还需先令num-1，对9取模，然后再令结果值+1。

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

[Wikipedia article]: https://en.wikipedia.org/wiki/Digital_root

发表评论取消回复

表情：

评论列表（有 0 条评论，177人围观）

还没有评论，来说两句吧...

相关阅读

相关 258 Add Digits

public int addDigits(int num) { while (num > 9) { n

Myth丶恋晨/ 2022年08月04日 10:50/ 0 赞/ 130 阅读

相关 leetcode-258.add digits/Digital root

leetcode-258.Add Digits Given a non-negative integer num, repeatedly add all its digi

痛定思痛。/ 2022年07月28日 00:13/ 0 赞/ 172 阅读

相关 LeetCode 258. Add Digits

为了保持了解比较有意思的解法算法，所以决定每天看几道LeetCode上面的题，现在开始：题目： Given a non-negative integer num, r

川长思鸟来/ 2022年07月27日 13:39/ 0 赞/ 182 阅读

相关 258. Add Digits

Given a non-negative integer `num`, repeatedly add all its digits until the result has o

本是古典何须时尚/ 2022年07月15日 01:27/ 0 赞/ 187 阅读

相关 258. Add Digits

Given a non-negative integer `num`, repeatedly add all its digits until the result has o

青旅半醒/ 2022年07月15日 01:27/ 0 赞/ 178 阅读

相关 [leetcode]--258. Add Digits

Question 258: > Given a non-negative integer num, repeatedly add all its digits until t

叁歲伎倆/ 2022年07月11日 15:57/ 0 赞/ 175 阅读

相关 [leetcode]: 258. Add Digits

1.题目描述 Given a non-negative integer num, repeatedly add all its digits until the resul

古城微笑少年丶/ 2022年06月16日 01:25/ 0 赞/ 308 阅读

相关 258.Add Digits

/ Given a non-negative integer num, repeatedly add all its digits until the res

女爷i/ 2022年06月09日 03:54/ 0 赞/ 164 阅读

相关 leetcode 258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has onl

雨点打透心脏的1/2处/ 2022年06月08日 13:24/ 0 赞/ 153 阅读

相关【Leetcode】258. Add Digits（数学）

Given a non-negative integer `num`, repeatedly add all its digits until the result has o

谁借莪１个温暖的怀抱￠/ 2022年01月20日 06:53/ 0 赞/ 429 阅读