This is the 28th day of my participation in the August Challenge

---

Related articles

LeetCode brush questions summary: LeetCode brush questions

1. Title Description

---

You add

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

Start with simple questions to brush, exercise their thinking ability, for the interview preparation ~

Second, train of thought analysis

---

• Look at the examples in the title, let’s clarify the idea ~

• Example 1:

  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) time without loops or recursion?Copy the code

• Although the advanced version tells us not to use loops or recursion.

• But let’s start with the dumb way.

• Endless loop, you add, add until the final value is one digit return!

AC code

---

• Conversion array cyclic crack method:

  class Solution { public int addDigits(int num) { while (true){ char[] str = String.valueOf(num).toCharArray(); if (num<10){ return num; } for (int i=0; i<str.length; i++){ num+=Integer.parseInt(String.valueOf(str[i])); }}}}Copy the code

  • 
  • Ha ha, directly out of time limit, prove this method does not work
  • The cycle method is no longer fragrant. Ow!

• Take touch cracking method:

  • First, let’s take a closer look at the pattern of the problem.
  • 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 up all the numbers, the modulo of 9 is the same thing as the initial number of 9, so if you keep adding up, you’re going to end up with the initial number of 9.
  • Why is that?
  • The value in every digit except the ones digit is passed(9 + 1)That’s what we get when we carry.
  • Consider the carry mechanism of the abacus.
  • Let me give you some examples

  int addDigits(int num)
  {
      if(0 == num % 9)
      {
          return 9;
      }
      return num % 9;
  }
  Copy the code

  • How can we simplify this?

    return (num - 1) % 9 + 1;
    Copy the code

  • The execution result

  • 

  • Therefore, some things are fixed laws, we should be good at summing up, good at discovery!

Four,

• Thousands of ideas to solve the problem, whether this method is good, or whimsical solution, can solve is a good way! White cat black cat can catch mice cat is a good cat!
• Here are a few other LeetCode solutions for reference!
• Click to jump: recursive solution
• Click to jump: mold solution

---

The road ahead is long, I see no end, I will search high and low

If you think I bloggers write well! Writing is not easy, please like, follow, comment and give encouragement to the blogger ~ Hahah