本文由本人@takooctopus对LeetCode每日打卡签到，做点记录。

258. Add Digits

题目描述

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example

Explanation:

The process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:

Could you do it without any loop/recursion in O(1) runtime?

Solution

{{- code -}}

我们主要要去考虑是否有O(1)的算法。

考虑题目假设有一个三位数abc，我们能够看见:

\begin{align}
abc &= 100a + 10b + c \\
sum &= a + b + c
\end{align}

两式相减我们能够看见多余的部分

\begin{align}
minus = 99a + 9b
\end{align}

明显的，多余的部分为9的倍数。

我们可以以9取模。

但是在这其中有两个特例：

• 一个是0，因为所有9的倍数最终都模0，而大于0的数最终都不会得0。
• 同理是9，我们只需让所有模9后为0的返回9就行了。