优化N的数字和

Question

Codewars 问题：（数字总和/数字根）

给定n，取n的数字之和。如果该值超过一位数，则继续以这种方式减少，直到产生一位数。输入将是一个非负整数。

测试用例：

16  -->  1 + 6 = 7
942  -->  9 + 4 + 2 = 15  -->  1 + 5 = 6
132189  -->  1 + 3 + 2 + 1 + 8 + 9 = 24  -->  2 + 4 = 6
493193  -->  4 + 9 + 3 + 1 + 9 + 3 = 29  -->  2 + 9 = 11  -->  1 + 1 = 2

我的代码：

#include <bits/stdc++.h>
using namespace std;

int singleDigit(int n)
{
   int ans;
   while (n > 0)
   {
      int lastDigit = n % 10;
      n /= 10;

      ans += lastDigit;
   }

   while (ans > 9)
   {
      int n1 = ans;
      ans = 0;
      while (n1 > 0)
      {
          int lastDigit = n1 % 10;
          n1 /= 10;

          ans += lastDigit;
      }
   }

   return ans;
}

int main()
{
    cout << singleDigit(49319366) << endl;

    return 0;
}

是否有更好或优化的方法来解决这个问题或降低时间复杂度？

Answer 1

此函数适用于非负整数，适应负数很简单。

int singleDigit(int n) 
{
    return (n-1) % 9 + 1;
}

它具有以下优点：

• 没有变量会忘记初始化
• 没有循环来犯差一错误
• 快

缺点是：

• 目前尚不清楚它如何或为何起作用

有关最后一个要点的更多信息，请参阅：

• 数字根的直接公式
• 负数模运算

Answer 2

这是时间和空间复杂度为 o(1) 的代码，用于求数字之和。

它基于“如果一个数的各位数字之和能被 9 整除，则该数能被 9 整除”的性质。

int AddDigits(int num) {
  if (num == 0) {
    return 0;
  } else {
    return (num - 1) % 9 + 1;
  }
}