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

describe

If there is a natural number a divisible by a natural number b, a is called a multiple of b and b is a divisor of A. The common divisor of several natural numbers is called the common divisor of these natural numbers. The greatest common divisor of the common divisor is called the greatest common divisor of the natural numbers.

Enter a and b, return the greatest common divisor of a and B.

Data range: 1≤ A, B ≤10^9

Advanced: Space complexity O(1), time complexity O(logn).

Violence for cycle

The easiest way to do it is just loop I ++ to find two numbers that are divisible at the same time, and then loop until I is equal to the smallest number.

/** * violence for loop *@param a
* @param b
* @return* /
public int gcd (int a, int b) {
   // write code here
   intmin=a>b? a:b;int commonDivisor=1;
   for (int i=1; i<=min; i++){if (a%i==0&&b%i==0){ commonDivisor=i; }}return commonDivisor;
}
Copy the code

It’s pretty simple, isn’t it? But that can’t be done on a cow.

Of course we can’t just call it a day.

improved

After writing the violence for loop, my first thought was to improve, to improve on the violence loop. Of course, I know there are many great solutions on the Internet, which may involve various formulas, but I wanted to see how far I could go.

I think the most that can happen between 1 and 100 is a multiple of 2, so you can figure out the multiple of 2 first, and then you can figure out the common divisor of the two numbers, and then you can reduce the computation time.

public int gcd1 (int a, int b) {
    int doubleCommonDivisor=1;
    while (a%2= =0&& b%2= =0){
        doubleCommonDivisor*=2;
        a=a/2;
        b=b/2;
    }
    intmin=a>b? a:b;int commonDivisor=1;

    for (int i=1; i<=min; i++){if (a%i==0&&b%i==0){ commonDivisor=i; }}return commonDivisor*doubleCommonDivisor;
}
Copy the code

Run!

Run through, but the time is longer, memory is good.

Except for the numbers of 2, it’s pretty hard to pull out multiples by themselves, because that’s the end of the road.

Toss and turn and divide

Learned more 🐂 algorithms from the big guy.

You just keep taking the larger number and decreasing it, and then taking the difference and the smaller number and subtracting it, and subtracting it until one of them is equal to 0, and you have the greatest common divisor.

For example, 10 and 30, the first time 30 minus 10=20; 20-10=10; Third time 10-10=0; So this is the small number 10 and the difference of 0, and this small number is the largest common divisor that we want.

If it’s a common divisor of 1, 17 and 30, the first time 30-17=13; Second time 17-13=4; Third time 13-4=9; The fourth time 9-4=5; Fifth time 5-4=1; And then we subtract all of them by 1, and we know that one of them is equal to 0, and we return 1;

Both the positive and negative examples are reasoned correctly.

/** * @param a * @param b * @return */ public int gcd2 (int a, int b) {if (b==0) { So we just have to see if b is equal to 0, and when B is equal to 0, a return A; } return a>b? gcd2(b,a-b):gcd2(a,b-a); }Copy the code

Run!

Running time is dozens of times faster, and the memory footprint is not much more, so it seems that the violent for loop is really hot.

Toss and turn and divide

More elegant than the toss and turn subtraction is the toss and turn division, faster efficiency, more stable.

Subtraction can easily achieve the same running time as the for loop in extreme cases (i.e., with a difference equal to one).

Toss and turn division can be said to be the same as toss and turn subtraction, is to change the subtraction to remainder.

You keep taking the larger number and dividing it by the smaller number, and then taking the remainder and the smaller number and dividing it all the way down, until one of them is equal to 0, and you have the greatest common divisor.

Continue with the 10 and 30 examples. 30%10=0; One time, we get the result. 10. Very fast.

If it’s a common divisor of 1, 17 and 30, 30% the first time, 17=13; Second time 17%13=4; The third time 13%4=1; 4 times 4%1=0; The fifth time, a number equal to 0, returns the greatest common divisor 1.

Both positive and negative cases are more efficient than the tossing and turning subtraction method.

Knock code!

@param a * @param b * @return */ public int gcd3 (int a, int b) {if (b==0) { So we just have to see if b is equal to 0, and when B is equal to 0, a return A; } return a>b? gcd3(b,a%b):gcd3(a,b%a); }Copy the code

Run!

Np! Run time and memory usage are not mentioned.

The last

The problem of finding the greatest common divisor has a high mathematical requirement, and it is difficult to achieve the optimal solution of this problem only by relying on their own coding common sense.

Summarize a rule:

Don’t iterate if you can, and don’t add or subtract if you can multiply and divide.

That’s all for today.

Here is a programmer Xu Xiaobai, daily algorithm [is] my new open a column, primary record my daily learning algorithm, here also hope that I can stick to the daily learning algorithm, don’t know whether this article style you like, don’t mean you free praise, your thumb up, collection, and comments are after work I insist on more power.