Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

preface

Today’s title is simple, and although it’s really simple, the progression is not that simple, and it involves a little bit of math.

A daily topic

Today’s daily question 258. The difficulty is simple

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

Example 1:

Enter num =38Output:2Explanation: The process of adding the members is:38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2Due to the2Is one digit, so return2.Copy the code

Example 2:

Enter num =0Output:0

Copy the code

Tip:

  • 0 <= num <= 231 – 1

 

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

Answer key

simulation

Add up each digit of a number and repeat until the result is less than 10. Then you can obtain the units digit by adding the remainder of num to 10. Then you can round down the remainder of num to 10. All the way until num is 0, and then we try to determine if all the units digits add up to less than 10. If so, the answer is given. If not, we repeat the process.

/ * * *@param {number} num
 * @return {number}* /
 var addDigits = function(num) {
    while (num >= 10) {
        let sum = 0;
        while (num > 0) {
            sum += num % 10;
            num = Math.floor(num / 10);
        }
        num = sum;
    }
    return num;
};
Copy the code

Mathematical thinking

The difficulty of this problem mainly lies in the advanced place, how to use O(1) time complexity to complete this problem, which generally can only use mathematical thinking to solve the problem, that is, to find rules.

Given the number num, we can see that it has two parts, one is the digit part, and one is everything except the units digit, so we can focus on one point, which is everything except the units digit, let’s say 240, and then its tens place plus its hundreds place is the remainder of 9.

And that makes a lot of sense. Let’s say 240 then we have 24 tens, each of which has a remainder of 9, so we have 24 ones, and in that case, the 2 is a ten-digit number, which has a remainder of 9, and we have 2 left, so we have 2 and 4, which is what they want us to figure out.

Plus the units digit is the same thing, you’re always subtracting the units digit, but the tens place and the hundreds place and the thousands place are equally divided by 10, and the number in each place is equally divided, and it’s going to be the same thing as the number that’s subtracted from 9.

And we can also see a pattern a little bit better with this picture, so we’re dealing with the special case, the case where it’s divisible by 9 and the case where it’s 0

/ * * *@param {number} num
 * @return {number}* /
 var addDigits = function(num) {
    if(num == 0) {return 0
    }
    if(num%9= =0) {return 9
    }
    return num%9
};
Copy the code