Skip to content

How do I use the greatest common divisor to kill the algorithm problem

There is a special study on the greatest common divisor. Although LeetCode does not directly let you solve the problem of the greatest common divisor. But there are some problems that indirectly require you to solve the greatest common divisor.

such as:

-914. Card Grouping -365. Kettle Problem -1071. The greatest common factor of a string

Therefore, how to find the greatest common divisor becomes important.

How to find the greatest common divisor?

Definition 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

Complexity Analysis

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

Toss and to divide

If we need to calculate the greatest common divisor of a and b, use the tossing division method. First, we first calculate the remainder c of dividing a by b, and transform the problem into finding the greatest common divisor of b and c; then, calculate the remainder d of dividing b by c, and transform the problem into finding the maximum of c and d Common divisor; then calculate the remainder e of dividing c by d, and transform the problem into finding the greatest common divisor of d and e. ..... By analogy, the operation between two larger integers is gradually transformed into an operation between two smaller integers until the two numbers can be divided evenly.

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

Complexity Analysis

-Time complexity: \(O(log(max(a, b)))\) -Space complexity: The space complexity depends on the depth of the recursion, so the space complexity is \(O(log(max(a, b)))\)

More phase reduction technique

If a and b are both large, the performance of a% b will be lower. In China, "Nine Chapters of Arithmetic" mentions a more phase subtraction technique which is similar to the toss and turns subtraction method. E7%AE%97%E8%A1%93#-.7BA.7Czh-hans:.E5.8D.B7.3Bzh-hant:.E5.8D.B7.7D-.E7.AC.AC.E4.B8 .80.E3.80.80.E6.96.B9.E7.94.B0.E4.BB.A5.E5.BE.A1.E7.94.B0.E7.96.87.E7.95.8C.E5.9F. 9F "More Subtraction Technique"). Its principle is: Two positive integers a and b (a>b), their greatest common divisor is equal to the difference c of ab 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)

The above code will report stack overflow. The reason is that if the difference between a and b is relatively large, the number of recursions will increase significantly, which is much greater than the recursion depth of the tossing and dividing method. The worst time complexity is O(max(a, b))). At this time, we can combine toss and turn to divide and more to subtract to make a combination, so that better performance can be obtained in various situations.

Visualization

Below we will give a vivid explanation of the above process. In fact, this is also the way of explanation in the textbook. I just copied it to increase my understanding. Let's explain through an example:

If we have a piece of land of 1680 meters* 640 meters, we want to talk about the land divided into several squares, and we want to make the side length of the square land as large as possible, how should we design the algorithm?

In fact, this is an application scenario of the greatest common divisor. Our goal is to solve the greatest common divisor of 1680 and 640.

Dividing the land of 1680 meters* 640 meters is equivalent to dividing the land of 400 meters* 640 meters. why? If the side length of a square divided by 400 meters* 640 meters is x, then 640% x == 0, then it must also meet the remaining two blocks of 640 meters* 640 meters.

We continue to perform the above segmentation:

Until the side length is 80, there is no need to proceed.

Example analysis

Title description

Given three numbers a, b, c, you need to find the value of the nth (n starts from 0) ordered sequence, which is composed of integer multiples of a, b, and c.

such as:
n = 8
a = 2
b = 5
c = 7

Since the ordered sequence composed of integer multiples of 2, 5, 7 is [1, 2, 4, 5, 6, 7, 8, 10, 12, ...], we need to return 12.

Note: We agree that the first in the ordered sequence is always 1.

Ideas

You can verify online through this site.

A simple idea is to use the heap to do it. The only thing that needs to be paid attention to is deduplication. We can use a hash table to record the numbers that have appeared in order to achieve the purpose of deduplication.

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))

For those who don’t understand this solution, let’s take a look at what I wrote before Almost finished all the problems in Likou, I found these things. . . (Second Bullet)

However, this approach is too time-complex, is there a better approach?

In fact, we can dichotomize the search space. First think about a problem. If a number x is given, how many values ​​are less than or equal to x in the ordered sequence.

The answer is x // a + x // b + x // c?

// is the floor except

Unfortunately not. For example, 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, one time is \(2 * 2 = 4\), and the other time is \(4 * 1 = 4\).

In order to solve this problem, we can adopt the knowledge of set theory.

A little collection of knowledge:

-If the set of values ​​less than or equal to x in an ordered sequence that are divisible by x and a multiple of a is SA, the set size is A -If the set of values ​​less than or equal to x in the ordered sequence that are divisible by x and a multiple of b is SB, the set size is B -If the set of values ​​less than or equal to x in the ordered sequence that are divisible by x and a multiple of c is SC, the set size is C

Then the final answer is the number of digits in the large set (need to be deduplicated) formed by SA, SB, and SC, that is:

\[ A + B + C-sizeof(SA \cap SB)-sizeof(SB \cap SC)-sizeof(SA \cap SC) + sizeof(SA \cap SB \cap SC) \]

The problem is transformed into how to find the number of intersections of sets A and B?

A and B, B and C, A and C, and even the intersection of A, B, and C are the same.

In fact, the number of intersections 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)

The next step is the two-point routine. If you don’t understand the two-point part, take a look at my two-point 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

Complexity Analysis

-Time complexity: \(logn\). -Space complexity: The depth of the recursion tree of gcd and lcm is basically negligible.

to sum up

Through this article, we not only understand the concept of the greatest common divisor and how to find it. I also visually perceive the principle of the greatest common divisor calculation. 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 too few in Lei Kou. You can find these questions through the Mathematics tab. For more about the mathematical knowledge in the algorithm, you can refer to this article Summary of math test points necessary to brush algorithm questions

The second part of this article will be released soon.