How did I use the “greatest common divisor” secant algorithm

There are special studies on the greatest common divisor. And in LeetCode, there’s no problem directly asking you to solve for the greatest common divisor. But there are some problems that indirectly require you to solve the greatest common divisor.

Such as:

• 914. Grouping of cards
• 365. The kettle problem
• 1071. The greatest common factor of a string

So how to solve the greatest common divisor is very important.

How do I find the greatest common divisor?

Define the method

def GCD(a: int, b: int) - >int:
    smaller = min(a, b)
    while smaller:
        if a % smaller == 0 and b % smaller == 0:
            return smaller
        smaller -= 1
Copy the code

Complexity analysis

• Time complexity: the best case is to execute the loop body once, the worst case is to smaller to 1, so the total time complexity is O(N)O(N)O(N), where N is the smaller number of a and B.
• Space complexity: O(1)O(1)O(1).

Toss and turn and divide

If we want to find the greatest common divisor of a and B, we can divide by tossing and turning. First, let’s calculate the remainder c of a divided by b, and convert the problem to finding the greatest common divisor of B and C; Then compute the remainder d of b divided by C, and turn the problem into finding the greatest common divisor of C and D; And then we can figure out the remainder of c divided by D, e, which turns the problem into finding the greatest common divisor of d and e. . And so on, gradually converting an operation between two larger integers into an operation between two smaller integers until the two numbers are divisible.

def GCD(a: int, b: int) - >int:
    return a if b == 0 else GCD(b, a % b)
Copy the code

Complexity analysis

• Time complexity: O (log (Max (a, b))) O (log (Max (a, b))) O (log (Max (a, b)))
• Spatial complexity: The spatial complexity depends on the depth of recursion, so the spatial complexity is O(log(Max (a,b)) O(log(Max (a,b)))O(log(Max (a,b)))

More phase reduction surgery

Toss and turn division if a and B are large, a % b performance will be low. In China, the Nine Chapters on Suanshu (Nine Chapters on Suanshu) refers to a method of reducing the loss of geng Xiang, which is similar to the subtraction method of tossing and turning. Its principle is: two positive integers A and B (a>b), their greatest common divisor is equal to the difference between A and B and the greatest common divisor of the smaller number b.

def GCD(a: int, b: int) - >int:
    if a == b:
        return a
    if a < b:
        return GCD(b - a, a)
    return GCD(a - b, b)
Copy the code

The above code will report a stack overflow. The reason is that if the difference between A and B is large, the recursion times will be significantly increased, which is much deeper than the recursive depth of toss and turn division, and the worst time complexity is O(Max (a, b)). At this point we can do a combination of toss and turn division and more phase reduction, so as to achieve better performance in all situations.

Visual interpretation

Now let’s explain the above process vividly in a table. In fact, this is also the way in the textbook. I just copy it and increase my understanding. Let’s go through an example:

Let’s say we have a piece of land 1680 meters by 640 meters, and we want to talk about the land divided into squares, and we want the sides of the square to be as large as possible, how do we design the algorithm?

In fact, this is the case for the greatest common divisor, and our goal is to find the greatest common divisor for 1680 and 640.

Dividing a land of 1,680 meters by 640 meters is equivalent to dividing a land of 400 meters by 640 meters. Why is that? If the side length of the square divided by 400 m * 640 m is x, then 640 % x == 0, then it must also satisfy the remaining two blocks of 640 m * 640 m.

We keep doing the above segmentation:

Until we get to 80, we don’t have to go any further.

Instance analysis

Topic describes

Given three numbers A, b, and c, you need to find the value of the NTH (n starts at 0) ordered sequence made up of integer multiples of a, b, and c. For example, n = 8, a = 2, b = 5, c = 7, the ordered sequence formed by integer multiples of 2, 5, 7 is [1, 2, 4, 5, 6, 7, 8, 10, 12... So we need to return 12. Note: we agree that the first of an ordered sequence is always 1.Copy the code

Train of thought

You can verify it online through this website.

A simple idea is to use the heap to do so, the only thing that needs to be noticed is to remove the weight, we can use a hash table to record the occurrence of the number, to achieve the purpose of removing the weight.

Code:

ss Solution:
    def solve(self, n, a, b, c) :
        seen = set()
        h = [(a, a, 1), (b, b, 1), (c, c, 1)]
        heapq.heapify(h)

        while True:
            cur, base, times = heapq.heappop(h)
            if cur not in seen:
                n -= 1
                seen.add(cur)
            if n == 0:
                return cur
            heapq.heappush(h, (base * (times + 1), base, times + 1))
Copy the code

For those who don’t understand this solution, I wrote almost all the pile problems, and I found these things… (Second shot)

However, this approach is too time intensive, is there a better way?

In fact, we can dichotomy the search space. Let’s start by thinking about how many values in an ordered sequence are less than or equal to x, given a number x.

Is the answer x // a + x // b + x // c?

// The floor is divided

Unfortunately not. If a = 2, b = 4, n = 4, the answer is obviously not 4 // 2 + 4 // 4 = 3, but 2. The reason for the error here is that 4 is calculated twice, once for 2∗2=42 * 2=42 ∗2=4, and again for 4∗1=44 * 1=44 ∗1=4.

To solve this problem, we can use our knowledge of set theory.

A little collective knowledge:

• If you take the ordered sequence of values less than or equal to x that are divisible by x and multiples of A, the set is SA, and the set size is a
• If you take the ordered sequence of values less than or equal to x that are divisible by x and multiples of B, the set is SB, and the set size is b
• If we take the ordered sequence of values less than or equal to x that are divisible by x and multiples of C, the set is SC, and the set size is C

So the final answer is the number of numbers in the large set of SA, SB and SC (to be de-duplicated), namely:

The question becomes how many sets of A and B intersect?

The intersection of A and B, B and C, A and C, even A, B, and C is the same thing.

In fact, the intersection number of SA and SB is x // LCM (A, B), where LCM is the least common multiple of A and B. The least common multiple can be calculated by the greatest common divisor:

def lcm(x, y) :
    return x * y // gcd(x, y)

Copy the code

Next is the dichotomy routine, dichotomy part do not understand the proposal to see my dichotomy topic.

Code (Python3)

class Solution:
    def solve(self, n, a, b, c) :
        def gcd(x, y) :
            if y == 0:
                return x
            return gcd(y, x % y)

        def lcm(x, y) :
            return x * y // gcd(x, y)

        def possible(mid) :
            return (mid // a + mid // b + mid // c - mid // lcm(a, b) - mid // lcm(b, c) - mid // lcm(a, c) + mid // lcm(a, lcm(b, c))) >= n

        l, r = 1, n * max(a, b, c)
        while l <= r:
            mid = (l + r) // 2
            if possible(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

Copy the code

Complexity analysis

• Time complexity: Lognlognlogn.
• Spatial complexity: The recursive tree depth of GCD and LCM is negligible.

conclusion

Through this article, we not only understand the concept of the greatest common divisor and the solution method. I also visually perceive the principle of the calculation of the greatest common divisor. The greatest common divisor and the least common multiple are two similar concepts. Questions about the greatest common divisor and the least common multiple are not few in the force buckle. You can find these questions through the math label. For more information about the mathematics of the algorithm, please refer to the summary of the necessary mathematics test points in this article

The second part of this article is coming soon.

That’s all for this article. If you have any opinion on this, please leave a message to me. I will check the answer one by one when I have time. More algorithms can be found in my LeetCode repository: github.com/azl39798585… . It already has 40K star. You can also pay attention to my public account “Li Kou Jia Jia” take you to bite the hard bone of the algorithm.