携手创造，一起生长！这是我参与「日新计划 8 月更文挑战」的第26天，点击检查活动详情

标题

给定一个非负整数 num，重复将各个位上的数字相加，直到成果为一位数。回来这个成果。

示例 1：

  • 输入： num = 38
  • 输出： 2
  • 解说： 各位相加的进程为：
    38 --> 3 + 8 --> 11
    11 --> 1 + 1 --> 2
    因为 2 是一位数，所以回来 2。

示例 2：

  • 输入： num = 0
  • 输出： 0

前言

这道题的本质是核算自然数 num\textit{num} 的数根。

数根又称数字根（Digitalroot\text{Digital root}），是自然数的一种性质，每个自然数都有一个数根。关于给定的自然数，重复将各个位上的数字相加，直到成果为一位数，则该一位数即为原自然数的数根。

核算数根的最直观的办法是模仿核算各位相加的进程，直到剩余的数字是一位数。使用自然数的性质，则能在 O(1)O(1) 的时刻内核算数根。

办法一：模仿

思路及解法

最直观的办法是模仿各位相加的进程，直到剩余的数字是一位数。

核算一个整数的各位相加的做法是，每次核算当时整数除以 10 的余数得到最低位数，将最低位数加到总和中，然后将当时整数除以 10。重复上述操作直到当时整数变成 0，此时的总和即为原整数各位相加的成果。

代码

class Solution {
    func addDigits(_ num: Int) -> Int {
        var num = num
        while num >= 10 {
            var sum: Int = 0
            while num > 0 {
                sum += num % 10
                num /= 10
            }
            num = sum
        }
        return num
    }
}

复杂度剖析

  • 时刻复杂度：O(log⁡num)O(\log \textit{num})，其间 num\textit{num} 是给定的整数。关于 num\textit{num} 核算一次各位相加需要 O(log⁡num)O(\log \textit{num}) 的时刻，因为 num≤231−1\textit{num} \le 2^{31} – 1，因而关于 num\textit{num} 核算一次各位相加的最大或许成果是 8282，关于任意两位数最多只需要核算两次各位相加的成果即可得到一位数。

  • 空间复杂度：O(1)O(1)。

办法二：数学

思路及解法

假设整数 num\textit{num} 的十进制表明有 nn 位，从最低位到最高位依次是 a0a_0 到 an−1a_{n – 1}，则 num\textit{num} 可以写成如下形式：

num=∑i=0n−1ai10i=∑i=0n−1ai(10i−1+1)=∑i=0n−1ai(10i−1)+∑i=0n−1ai\begin{aligned} \textit{num} &= \sum_{i = 0}^{n – 1} a_i \times 10^i \\ &= \sum_{i = 0}^{n – 1} a_i \times (10^i – 1 + 1) \\ &= \sum_{i = 0}^{n – 1} a_i \times (10^i – 1) + \sum_{i = 0}^{n – 1} a_i \end{aligned}

当 i=0i = 0 时，10i−1=010^i – 1 = 0 是 99 的倍数；当 ii 是正整数时，10i−110^i – 1 是由 ii 位 99 组成的整数，也是 99 的倍数。因而关于任意非负整数 ii，10i−110^i – 1 都是 99 的倍数。由此可得 num\textit{num} 与其各位相加的成果模 99 同余。重复核算各位相加的成果直到成果为一位数时，该一位数即为 num\textit{num} 的数根，num\textit{num} 与其数根模 99 同余。

咱们对 num\textit{num} 分类讨论：

  • numnum 不是 99 的倍数时，其数根即为 num\textit{num} 除以 99 的余数。
  • numnum 是 99 的倍数时：

    • 如果 num=0\textit{num} = 0，则其数根是 00；
    • 如果 num>0\textit{num} > 0，则各位相加的成果大于 00，其数根也大于 00，因而其数根是 99。

细节

根据上述剖析可知，当 num>0\textit{num} > 0 时，其数根的成果在范围 [1, 9] 内，因而可以想到核算 num−1\textit{num} – 1 除以 99 的余数然后加 11。因为当 num>0\textit{num} > 0 时，num−1≥0\textit{num} – 1 \ge 0，非负数除以 99 的余数必定也对错负数，因而核算 num−1\textit{num} – 1 除以 99 的余数然后加 11 的成果是正确的。

当 num=0\textit{num} = 0 时，num−1=−1<0\textit{num} – 1 = -1 < 0，负数对 99 取余或取模的成果的正负在不同言语中有所不同。

  • 关于取余的言语，成果的正负和左操作数相同，则 num−1\textit{num} – 1 对 99 取余的成果为 −1-1，加 11 后得到成果 00，可以得到正确的成果；

  • 关于取模的言语，成果的正负和右操作数相同，则 num−1\textit{num} – 1 对 99 取模的成果为 88，加 11 后得到成果 99，无法得到正确的成果，此时需要对 num=0\textit{num} = 0 的情况专门做处理。

代码

class Solution {
    func addDigits(_ num: Int) -> Int {
        return (num - 1) % 9 + 1
    }
}

复杂度剖析

  • 时刻复杂度：O(1)O(1)。

  • 空间复杂度：O(1)O(1)。