This is the 15th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021.

Title description:

258. Add It all up – LeetCode (leetcode-cn.com)

Given a non-negative integer num, repeatedly add the digits in each bit until the result is a single digit.

The sample a

Input: 38 Output: 2 Explanation: The process of adding the digits is: 3 + 8 = 11, 1 + 1 = 2. Since 2 is a single digit, return 2.Copy the code

Advanced:

Can you solve this problem in O(1)O(1)O(1) time without loops or recursion?

Thought analysis

mathematics

In order to advance, O(1)O(1)O(1) time complexity is required, so the ergodic and recursive solutions of the first reaction are definitely not in line with the meaning of the question. Generally, such solutions are mathematical solutions.

  • The integers that are divisible by 9 must also be divisible by 9 if they add up, so if you keep adding them up, you end up with 9.
  • Integers that are not divisible by 9, if you add them up, you get the magnitude of 9, which is the same thing as taking the magnitude of the initial number, so if you keep adding them up, you’re going to end up with the magnitude of 9.

AC code

class Solution {
    public int addDigits(int num) {
        return (num - 1) % 9 + 1; }}Copy the code

conclusion

This kind of problem, the solution seems to be a simple line, but the math behind it is the key to the solution.

This problem solution in mathematics is actually called the number root, as for what is the number root I will not explain, the elder brother’s answer is very detailed, we can refer to reference. Detailed popular analysis of ideas, multiple solutions – you add – force buckle (LeetCode) (leetcode-cn.com), there are derivations of the process, interested in their own access.

reference

[Java] O(1) Solution – LeetCode (leetcode-cn.com)

Remainder divisible by 9 – Add them all – LeetCode (leetcode-cn.com)

258. Add You up – Add You Up – LeetCode (leetcode-cn.com)