问题

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

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input: 38
Output: 2
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?

  • Level: Easy

  看完题目，之后列举了几个。分别是小于9的，是9的倍数，不是9的倍数。进行归纳如下:

  1. n < 9 直接返回n；
  2. n mod 9 = 0 直接返回9, 比如n=18
  3. n mod 9 != 0 直接返回 n mod 9

后面看到讨论中，说是 digit root problem2。

根据上述的分析，可以直接写出解法，具体如下：

1
2
3
4
5
6
7
8
9
10
public int addDigits(int num) {
    if (num < 10) {
        return num;
    }
    int result = num % 9;
    if (result != 0) {
        return result;
    }
    return 9;
}

分析

  • 时间复杂度为O(1)；

相关资料

  1. 1.https://leetcode.com/problems/add-digits/description/ ↩
  2. 2.https://en.wikipedia.org/wiki/Digital_root ↩