76 - 各位相加

题目

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

示例:

输入: 38 输出: 2

解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。

进阶: 你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？

解答

题目里提示了有两种方法：循环和递归。

如果要在O(1)时间内解决，我猜是要用位操作了

递归

感觉递归最容易想到😂

var addDigits = function (num) {
  if (num.toString().length === 1) {
    return num
  }
  let result = 0
  while (num) {
    result += num % 10
    num = Math.floor(num / 10)
  }
  return addDigits(result)
};

Runtime: 84 ms, faster than 20.69% of JavaScript online submissions for Add Digits.

Memory Usage: 36 MB, less than 66.67% of JavaScript online submissions for Add Digits.

这个效率有点慢。

func addDigits(num int) int {
    if len(strconv.Itoa(num)) == 1 {
        return num
    }
    var result int
    for num != 0 {
        result += num % 10
        num /= 10
    }
    return addDigits(result)
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Add Digits.

Memory Usage: 2.2 MB, less than 50.00% of Go online submissions for Add Digits.

go：即使用垃圾算法我也能0ms算出来😂

其实这是一道数学题

各数相加，在数学上被叫做数根(Digital root)，不过中文维基啥都没写，英文的比较丰富一些

然而我还是看不懂。。然后又顺着“数根”这个关键词，搜到了知乎上的证明和英文证明和csdn的证明

写一下我的理解：

题目是，给一个数字n，让我们求其数根r。我们以三位数为例，做一些假设：

• 假设$n=100a+10b+c$，其中的a, b, c都是整数。

• 所以我们要求的$r=a+b+c$

  而且我们求的这个r是个位数，因此$0<r<10$

那么n与r有什么联系呢？

$$\begin{align} n&=100a+10b+c \\ &=(99+1)a+(9+1)b+c \\ &=(99a+9b)+(a+b+c) \\ &=9(11a+b)+r \\ \end{align}$$

因为a与b都是整数，所以$11a+b$也是整数，我们用N来代替，也就是说

$$n=9N+r$$

换言之，n是r加上9的倍数，也就是说

$$r=n\%9$$

• 假设这个换算函数是dr()，也就是$dr(n)=r$。

又因为个位数的数根就是它本身。也就是说

$$dr(r)=r=dr(n\%9)$$

又因为$n\%9$是个位数，因此

$$dr(r)=n\%9$$

当然这里有个特殊情况：$n=9$或是9的倍数

此时我们要求的$r$是9，但用式8的取余方法，得出来的结果是0。

因此，当取余结果为0的时候，我们就令$r=9$，打上这个补丁

那么当$n=0$的时候，岂不是会返回9吗？因此得再打一个补丁

\begin{equation} dr(n)= \begin{cases} 0&{\mbox{if}}\ n=0,\\ 9&{\mbox{if}}\ n\neq 0,\ n\ \equiv 0{\pmod {9}},\\ n\ {\rm {mod}}\ 9&{\mbox{if}}\ n\not \equiv 0{\pmod {9}} \end{cases} \end{equation}

维基百科上面还有个更简洁的公式：

$$dr(n)=1\ +((n-1)\ {\rm {mod}}\ 9)$$

变成代码怎么写呢？

var addDigits = function (num) {
  if (num===0) {
    return 0
  }
  if (num % 9 === 0) {
    return 9
  } else {
    return num % 9
  }
};

Runtime: 68 ms, faster than 88.09% of JavaScript online submissions for Add Digits.

Memory Usage: 35.4 MB, less than 100.00% of JavaScript online submissions for Add Digits.

数学的力量。。。

还有人强行变成一行代码😂

var addDigits = function (num) {
  return num === 0 ? 0 : (num % 9 === 0 ? 9 : num % 9)
};

Runtime: 76 ms, faster than 52.60% of JavaScript online submissions for Add Digits.

Memory Usage: 35.5 MB, less than 100.00% of JavaScript online submissions for Add Digits.

属于那种，虽然看起来很骚，但没什么用，而且别人也不容易看懂，的操作。。

var addDigits = function (num) {
  return 1+(num-1)%9
};

Runtime: 76 ms, faster than 52.60% of JavaScript online submissions for Add Digits.

Memory Usage: 35.5 MB, less than 100.00% of JavaScript online submissions for Add Digits.

func addDigits(num int) int {
    if num == 0 {
        return 0
    }
    if num%9 == 0 {
        return 9
    } else {
        return num % 9
    }
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Add Digits.

Memory Usage: 2.2 MB, less than 100.00% of Go online submissions for Add Digits.

func addDigits(num int) int {
    return 1 + (num-1)%9
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Add Digits.

Memory Usage: 2.2 MB, less than 100.00% of Go online submissions for Add Digits.