LeetCode 力扣官方题解 | 258. 各位相加
题目描述
难易度：简单
输入: num = 38输出: 2解释: 各位相加的过程为：38 --> 3 + 8 --> 1111 --> 1 + 1 --> 2由于 2 是一位数，所以返回 2。
示例 2：
输入: num = 0输出: 0
提示：
0 <= num <= 231 - 1
解决方案
前言
这道题的本质是计算自然数 num 的数根。
数根又称数字根（Digital root），
是自然数的一种性质，每个自然数都有一个数根。对于给定的自然数，反复将各个位上的数字相加，直到结果为一位数，则该一位数即为原自然数的数根。
计算数根的最直观的方法是模拟计算各位相加的过程，直到剩下的数字是一位数。利用自然数的性质，则能在 O(1) 的时间内计算数根。
方法一：模拟
思路和算法
最直观的方法是模拟各位相加的过程，直到剩下的数字是一位数。
计算一个整数的各位相加的做法是，每次计算当前整数除以 10 的余数得到最低位数，将最低位数加到总和中，然后将当前整数除以 10。重复上述操作直到当前整数变成 0，此时的总和即为原整数各位相加的结果。
代码
Java
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;}}
C#
public 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;}}
C++
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;}};
C
int addDigits(int num){while (num >= 10) {int sum = 0;while (num > 0) {sum += num % 10;num /= 10;}num = sum;}return num;}
JavaScript
var addDigits = function(num) {while (num >= 10) {let sum = 0;while (num > 0) {sum += num % 10;num = Math.floor(num / 10);}num = sum;}return num;};
Python3
class Solution:def addDigits(self, num: int) -> int:while num >= 10:sum = 0while num:sum += num % 10num //= 10num = sumreturn num
Golang
func addDigits(num int) int {for num >= 10 {sum := 0for ; num > 0; num /= 10 {sum += num % 10}num = sum}return num}
复杂度分析
时间复杂度：O(log num)，其中 num 是给定的整数。对于 num 计算一次各位相加需要 O(log num) 的时间，由于 num ≤ 231 - 1，因此对于 num 计算一次各位相加的最大可能结果是 82，对于任意两位数最多只需要计算两次各位相加的结果即可得到一位数。
空间复杂度：O(1）。
方法二：数学
思路和算法
假设整数 num 的十进制表示有 n 位，从最低位到最高位依次是 a0 到 an−1，则 num 可以写成如下形式：
当 i = 0 时，10i - 1 = 0 是 9 的倍数；当 i 是正整数时，10i − 1 是由 i 位 9 组成的整数，也是 9 的倍数。因此对于任意非负整数 i，10i − 1 都是 9 的倍数。由此可得 num 与其各位相加的结果模 9 同余。重复计算各位相加的结果直到结果为一位数时，该一位数即为 num 的数根，num 与其数根模 9 同余。
我们对 num 分类讨论：
num 不是 9 的倍数时，其数根即为 num 除以 9 的余数。
num 是 9 的倍数时：
如果 num = 0，则其数根是 0；
如果 num > 0，则各位相加的结果大于 0，其数根也大于 0，因此其数根是 9。
细节
根据上述分析可知，当 num > 0 时，其数根的结果在范围 [1,9] 内，因此可以想到计算 num − 1 除以 9 的余数然后加 1。由于当 num > 0 时，num − 1 ≥ 0，非负数除以 9 的余数一定也是非负数，因此计算 num − 1 除以 9 的余数然后加 1 的结果是正确的。
当 num = 0 时，num − 1 = − 1 < 0，负数对 9 取余或取模的结果的正负在不同语言中有所不同。
对于取余的语言，结果的正负和左操作数相同，则 num − 1 对 9 取余的结果为 -1，加 1 后得到结果 0，可以得到正确的结果；
对于取模的语言，结果的正负和右操作数相同，则 num − 1 对 9 取模的结果为 8，加 1 后得到结果 9，无法得到正确的结果，此时需要对 num = 0 的情况专门做处理。
代码
Java
class Solution {public int addDigits(int num) {return (num - 1) % 9 + 1;}}
C#
public class Solution {public int AddDigits(int num) {return (num - 1) % 9 + 1;}}
C++
class Solution {public:int addDigits(int num) {return (num - 1) % 9 + 1;}};
C
int addDigits(int num){return (num - 1) % 9 + 1;}
JavaScript
var addDigits = function(num) {return (num - 1) % 9 + 1;};
Python3
class Solution:def addDigits(self, num: int) -> int:return (num - 1) % 9 + 1 if num else 0
Golang
func addDigits(num int) int {return (num-1)%9 + 1}
复杂度分析
时间复杂度：
空间复杂度：
BY /
本文作者：力扣
编辑&版式：Janson
声明：本文归“力扣”版权所有，如需转载请联系。
点个在看，少个 bug
微信扫码关注该文公众号作者