为何我的HackerRank Recursive Digit Sum解决方案被拒？

核心问题：超时而非结果错误 #

你的代码逻辑是正确的，但无法处理大规模输入，导致运行时间超过题目限制，这就是只通过约2/3测试用例的原因。

具体原因 #

当输入的字符串n长度极大（比如10^{5位），且`k`取值很大（比如10}5）时，n*k会生成一个长度为10^10的超长字符串：

• 这会占用巨量内存，甚至触发内存溢出；
• 每次循环遍历整个字符串求和的时间成本极高，远远超出题目允许的时间阈值。

而参考方案利用了**数字根（Digital Root）**的数学性质，完全不需要生成超长字符串，直接通过公式计算，效率呈数量级提升。

数字根的原理 #

超级数字本质就是数字根，其数学规律为：

1. 对于非零整数x，数字根为9（当x是9的倍数时），否则为x%9；
2. 若x=0，数字根为0。

参考方案中的公式1 + (k * sum(int(x) for x in n) - 1) % 9是数字根的另一种写法，能统一处理除x=0外的所有情况（若题目中n不会全为0，则无需额外判断）。

优化你的解决方案 #

你可以保留迭代求和的思路，但先计算n的数位总和再乘以k，避免生成超长字符串，这样就能通过所有测试用例：

def superDigit(n, k):
    total = sum(int(c) for c in n) * k
    # 迭代求数字根
    while total >= 10:
        total = sum(int(d) for d in str(total))
    return total

或者直接用数字根公式进一步优化效率：

def superDigit(n, k):
    total = sum(int(c) for c in n) * k
    if total == 0:
        return 0
    return total % 9 if total % 9 != 0 else 9

内容的提问来源于stack exchange，提问作者P-Sides