LeetCode OJ:Add Digits(数字相加)

  Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.文章来源地址:https://www.yii666.com/article/764058.html

  For example:

  Given num = 38, the process is like: 3 + 8 = 111 + 1 = 2. Since 2 has only one digit, return it.

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

想要做出来很简单,但是关键在于这里的最后一句话,要在O(1)时间内,而且不能使用循环或者递归。

这里就要说说有关数字根的概念了:

定义

数字根(Digital Root)就是把一个数的各位数字相加,再将所得数的各位数字相加,直到所得数为一位数字为止。而这个一位数便是原来数字的数字根。适用范围为正整数和零。例如:

1的数字根为1网址:yii666.com

10的数字根为1(1+0=1)

21的数字根为3(2+1=3)

48的数字根为3(4+8=12,1+2=3)文章来源地址https://www.yii666.com/article/764058.html

198的数字根为9(1+9+8=18,1+8=9)

性质说明

1.任何数加9的数字根还是它本身。

       小学学加法的时候我们都明白,一个数字加9,就是把十位加1,各位减1。因此十位加个位的和是不变的;如果有进位,即十位上是9,那么进位之后十位会变成0,百位会加1,道理和一个一位数加9是一样的。

2.9乘任何数字的数字根都是9。

      同样是小学时学乘法时,我们在计算一位数乘九的时候,把十只手指头排开,乘几便弯下第几只手指头,前后的手指个数便是那个结果。它的数字根永远是10-1=9。多位数的化,拆分每一位数字即可。

3.数字根的三则运算

  1.两数之和的数字根等于这两个数的数字根的和数字根

       对于两个一位数来说,很容易理解。因为一位数的数字根就是它本身。
       对于多位数来说,由性质1,把每个数字mod 9,就又变成了两个一位数。

  2.两数之积的数字根等于这两个数的数字根的积的和数字根

       可以把每个数字拆成许多9相加的形式,最后各剩余一个 (a mod 9), 由
            (a1+a2+...)*(b1+b2+...)=a1*(b1+b2+...)+a2*(b1+b2+...)+...+an*bm
       从a1到a[n-1]都是9,由性质2,原来两式的数字根就是(an*bm)的数字根。而由性质1,可知an,bm又是两数本身的数字根。

  3.一个数字的n次幂的数字根等于这个数字的数字根的n次幂的和数字根

  这一部分是转载 数字根介绍 的;网址:yii666.com<

  所以可以得知计算数字根的公式就是:root = (num - 1) % 9 + 1;  PS:这里的 -1主要是为了避免num正好是9的倍数,那样数根应该正好是9, 而不应该是0才对。

  代码不言而喻,只不过道理应该想清楚才对:

  考虑一下 result = (num - 1) % 9 + 1; 那么就有

      result - 1 = (num - 1) % 9; 那么 digitRoot(result - 1) == digitRoot(num - 1);

  那么根据上面所说的,就有:result的数字根与num的数字根就是一样的了。所以这个等式成立。文章地址https://www.yii666.com/article/764058.html

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

java版本代码如下所示:

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

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png