数的各位相加

今天做LeetCode的时候,发现这样一道题,是简单的题,不过有一点点奇特

题目让将一个数字的各位相加,出来的结果如果不是个位数,那么就再次相加,直到结果是个位数,这个个位数就是题目的结果

原题如下:

题目

最直接的想法是按照这个题意来,如果发现加出来的结果不是个位数,那就再加一遍,代码如下:

class Solution {
    public int addDigits(int num) {
        while (num >= 10) {
            int sum = 0;
            while (num > 0) {
                sum += num % 10;
                num /= 10;
            }
            num = sum;
        }
        return num;
    }
}

但是它题目下面还有一个要求:不使用循环和递归,并且在O(1)时间内完成(它写的是Follow up,我当做是必须的要求)

思考一下,应该是有什么规律,否则不可能实现这个要求的,所以写出了一部分数字,然后发现结果是1-9一直循环,所以将修改了代码:

class Solution {
    public int addDigits(int num) {
        if (num < 10)
            return num;
        num = num % 9;
        return num == 0? 9: num;
    }
}

提交了之后是正确的,但是我自己现在解释不了这个代码,所以还要再仔细研究一下这个规律

考虑两位数[10, 100),他们各位数和的范围是1-18,假设它们都需要两遍和,第一遍数字范围1-18,第二遍变为1-9

第一遍:

每增加一个数,和也会增加1,假设sum(x)是x各位数的和,那么这时候sum(x+1) = sum(x)+1

较为特殊的是39到40,前者39 => 12, 后者40 => 4,其实是个位数减9,十位数加1,那么它们的各位和符合:sum(x+1) = sum(x) - 9 + 1

综合来说,第一遍有sum(x+1) = sum(x) + 1或者是sum(x+1) = sum(x) - 9 + 1两种情况

第二遍:

[1-18]这个范围内sum(x) = x % 9(当值为0的时候应该取值为9)成立

这样的话对于两位数sum(x+1) = (sum(x)+1) % 9或者是sum(x+1) = (sum(x)+1-9) % 9,对于后边这个式子,-9可以省略掉,所以合并之后就是

sum(x+1) = (sum(x) + 1) % 9 (当结果为0时,取值为9)

这是两位数的情况,三位数的话第一遍和的结果范围变为[1, 27],第二遍范围[1, 18],第三遍[1, 9]
...
12位,范围为[1, 108],第二遍范围[1, 18],第三遍[1, 9]
...

最终可以得出sum(x+1) = (sum(x) + 1) % 9 (当结果为0时,取值为9)可以一直成立下去

那么sum(x) = x % 9(结果为0时,取9)就是成立的,这就是我第二段代码的原理

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 4,239评论 0赞 2
  • 定点小数运算 来自:http://www.eepw.com.cn/article/17893.htm 在DSP世界...
    郝宇峰阅读 10,127评论 0赞 2
  • 雨落煮茶无眠, 孤坐中堂寂静。 一炉沉香,两城相隔, 三寸相思,四千里瞬间。 岁月如画墨染江山, 竟欲长歌日月唱春...
    手握瓷杯阅读 753评论 0赞 6
  • 生活离我所熟悉的环境越来越远,离预期也越来越远,未来变得模糊不清,恐慌倒不至于,就是不适应。 公公昨晚风尘仆仆地来...
    叶的日子阅读 241评论 0赞 1
  • 你朋友圈里更新了信息:还有比一个人吃火锅更孤独的事吗?文字下面配了一张图片,图片里正在煮的火锅和桌子上你已调好的酱...
    木杪杪阅读 983评论 9赞 10

友情链接更多精彩内容