Sorted GCD Pair Queries | LeetCode 3312 - Python

[00:00:00]Hello everyone, I'm Paul and this is problem 3312.

[00:00:04]Sorted GCD pair queries. This is a very hard math problem, so don't worry if you didn't solve it first try.

[00:00:13]I don't think that you have ever seen something like this in a job interview.

[00:00:16]So with this in mind, let's see how to solve it step by step. We are given an integer array nums and an integer array queries. So let's say that we are given this input. And there is an array GCD pairs with all the GCDs or greatest common divisors of all possible pairs in the array nums sorted in ascending order.

[00:00:39]For each query, we have to find the element at the given index in this array GCD pairs. If we're given this array, here we have three pairs, two three, two four, and three four. So what's the GCD of the pair two three?

[00:00:55]Well, the divisors of number two are one and two. The divisors of number three are one and three. So the greatest common divisor here is one.

[00:01:05]If we take the pair two four, the greatest common divisor is two. And if we take the pair three four, the greatest common divisor is one. Now, this array GCD pairs has these elements in sorted order. So we will have something like one one two.

[00:01:24]And now we have to use this array to answer these queries. What element do we have here at index zero? We have a one, so the result of this query is one. At index two, we have a two. So the result here is two, and the result here is two.

[00:01:40]We need to return an array with these results. This is the final output. The main problem here is in the constraints.

[00:01:46]Let's say that we are going to build this array GCD pairs.

[00:01:51]Well, in order to do this, we have to iterate all pairs. We can do this with a nested for loop in big of n squared and complexity. But here in the constraints it says that n can be up to 10 to the power of five and this to the power of two is a very large number which we can't handle. So, the question is, how can we get the corresponding indices in queries without building this array directly?

[00:02:17]The solution is quite complex so here I made a road map. We'll go step by step starting from point one.

[00:02:24]First we need to get the frequencies of the array that we are given. Then we will transform the array of frequencies into an array where every element is the number of elements divisible by the corresponding index. Then we will transform these elements into pairs where both numbers are divisible by the index. Then we will transform the array again into an array where every element is the number of pairs with a GCD of the index. Then we will transform elements such that we get the number of pairs with a GCD of the current index or less.

[00:02:58]And finally with this final array we can answer queries using binary search. So, let's start with point one. How do we get the frequencies of elements in an array? Well, with a frequency map. In this scenario we will use an array. So, we iterate elements from left to right.

[00:03:18]We start with two. We go to the index two and add one to the frequency. This is one. Next we have a three so we go to the corresponding index and add one.

[00:03:29]Next we have a four so we go here and add one. So, the length of this array is four. We are considering the maximum number in the array plus one to actually include this number. In this scenario we have five elements. Now we need to transform the array into another one where each element is the number of elements that are divisible by the corresponding index. How do we do this?

[00:03:53]Well, maybe you're familiar with something called sieve of Eratosthenes.

[00:03:58]We use this to get a list of prime numbers. In this case, we will use it to get the number of elements that are divisible by each index. So, we are running this nested for loop, very similar to sieve of Eratosthenes. From every index, we are iterating every other index in steps of the current index starting from the current index times two. So, we start from index one because there's no number that's divisible by zero. So, here we put zero.

[00:04:30]Now, we are standing here. We have to iterate every other index starting from the current number times two.

[00:04:37]And we go up to the maximum number plus one, but this is non-inclusive, so we go up to this index. And we are moving in steps of I. Here, I is one, so we are moving in steps of one. First, we are here, then here, then here. Now, first we are looking at this index. Every time we take the current value and add the new value. 0 + 1 is 1, so here we put a 1. Next, the shape pointer is here, so we are looking at this number. We take the current value plus one, and the result is two.

[00:05:08]Next, shape here, so we are looking at one. 1 + 2 is equal to three. So, array at index one is equal to three, which means that we have these three numbers that are divisible by one. Now, we can continue with the next index. Now, we are moving in steps of two, and we start from 2 * 2, meaning four. We take the current value plus the new value, and 1 + 1 is two.

[00:05:33]And we have to move two steps forward.

[00:05:36]Now, we are out of bounds, so the final number here is two. And this makes sense because we have two numbers that are divisible by two. Those numbers are two and four. The frequencies are one and one. Next, we're looking at numbers that are divisible by three. And we need to start from three times two, meaning six.

[00:05:55]Six is out of bounds, so we keep this number only. Here, we put the one.

[00:05:59]Finally, for numbers that are divisible by four, we start from four times two.

[00:06:03]This is out of bounds, so we only have one. Here, we put one.

[00:06:07]Now, we need to get the number of pairs where both numbers are divisible by the current index. For example, we have three numbers that are divisible by one.

[00:06:17]How many pairs can be formed with three elements? For this, you should be familiar with something called combinatorics.

[00:06:25]So, let's see how this works. Here, we are looking for the number of pairs in three elements. Let's say that we have these three elements. This would be one possible pair. This would be another valid pair, and this would be another valid pair. The result of this would be three pairs. Now, how do we get these pairs? Well, with this formula down here. We say that nCr is equal to n factorial divided r factorial times n minus r factorial. In this scenario, we are looking for combinations of pairs, meaning two elements in three elements.

[00:07:01]So, we can do three factorial divided by two factorial times three minus two factorial.

[00:07:11]And this is equal to three times two, six divided by two, meaning three. Okay?

[00:07:19]So, the number of pairs in zero elements is zero. The number of pairs in three elements is three.

[00:07:25]The number of pairs in two elements is one. Because we only have two elements, so we have only one possible pair. If we use this formula, we say that two C two is equal to two factorial divided two factorial times two minus two factorial and this is equal to one. The number of pairs in one element is zero and the number of pairs in one element is zero.

[00:07:54]And by the way, don't worry about this formula. In Python, we have a function comb which takes n and r. So, we don't have to worry about this. We will use this in the code. But now, you know how this works. Now, we can transform this array into another one where every value is the number of pairs with a GCD of the current index.

[00:08:17]So, how do we do this? Well, first we need to understand how GCD works. If we take the GCD of numbers two and three, the result is one. If we take the GCD of numbers two and four, the result is two. So, the GCD is always smaller or equal to the smallest number that we are using to get the result.

[00:08:43]This is very important because the maximum possible GCD that we can have in the array nums is given by the maximum value in the array. In the worst case here, we could have two fours, in which case the largest GCD would be four. So, this means that the number of pairs where both numbers are divisible by four is the number of pairs with a GCD of four because this happens to be the maximum number in this input. So, here at index four, we use a zero and next we continue with this index.

[00:09:18]Next, we are here. How many pairs do we have with a GCD of exactly three?

[00:09:24]Well, the number of pairs where both numbers are divisible by three is zero.

[00:09:29]So, here we can put a zero.

[00:09:31]Now, we are here and this will make sense. How many pairs do we have with a GCD of exactly two. Well, remember that two is a divisor of number four and four is in within our range. So, what do we put here? Well, we need to take the number of pairs where both the numbers are divisible by two. We have that number here and subtract the number of pairs with a GCD of exactly the corresponding number. Remember that two is a divisor of four, so we go to this number and the value is zero. We do 1 - 0 and the result is 1. And you can see how we are doing this in the code.

[00:10:09]This is very similar to sieve of Eratosthenes again. Next, we are here at 1. And remember that these three numbers are divisible by 1. So, how many pairs do we have with a GCD of exactly 1?

[00:10:24]Well, we can take the number of pairs where both numbers are divisible by 1.

[00:10:28]We have that number here and subtract the corresponding values for indices that use the current index as a valid divisible number. So, [snorts] we are iterating numbers from I * 2, meaning 2, up to the maximum number + 1, but this is not included, so we go up to this point. First, we are here.

[00:10:51]Um 3 - 1 is equal to 2, so here we put 2. Next, we are here. 2 - 0 is 2. Next here, 2 - 0 is 2.

[00:11:01]And finally here, we get 0. And this makes sense because we have two pairs with a GCD of exactly 1. The pairs are 2 3 and 3 4. Remember that the pair 2 4 has a GCD of 2. That's the only pair with this GCD and that's why here we have a 1. Now, here we have a numbers of pairs with exact GCDs, which is great, but we still don't have the corresponding format to run queries.

[00:11:32]Just to be clear, this array corresponds to an array with two pairs with a GCD of one, so we have one one, and one pair with a GCD of two. Then we have two. And as you can see, this would be the array GCD pairs. Now, instead of building this array, given that this is very inefficient, what we are doing instead is running a prefix sum on this array.

[00:11:58]And remember how prefix sum works. At every index, we have the current value plus the previous augmented value. 0 + 0 is 0. Then 2 + 0 is 2. 2 + 1 is 3. 3 + 0 is 3. And 3 + 0 is 3.

[00:12:13]So now every value here corresponds to the number of pairs with a GCD of the current index or less. And now we can use this array to answer queries with binary search.

[00:12:25]But these queries are zero-indexed and this array is one-indexed. Here we have a zero, and we don't care about this number. It's as if we had a zero here.

[00:12:36]If we add a zero, we should add one to each query. So here we are looking for one, here we look for three, and here we look for three.

[00:12:44]Now, what if we run a binary search with one on this array? Well, that would give us index one. We can fit the one in between zero and two, right? So the result of this query would be one.

[00:12:57]If we try to put a three in this array, we can put it in between two and three.

[00:13:04]Here.

[00:13:05]So the result will be 0 1 2.

[00:13:08]And here we have the same query, so here we put another two.

[00:13:12]And just to be clear, remember that here we have two pairs with a GCD of exactly one. So if we are looking for the values in this array at index two, and we transform this into a one-indexed array, meaning this array plus a zero to the left, we can run a binary search here using three instead of two, and that will give us index two. Remember that these indices are GCDs. This result is formed by GCDs.

[00:13:44]Time complexity to get frequencies would be big O of the amount of elements, meaning N.

[00:13:50]Time complexity for this, here we get the amount of elements that are divisible by each index. This requires big O of the maximum number log the maximum number.

[00:14:02]Then, uh we have to get the number of pairs where both numbers are divisible by I.

[00:14:08]Here we use some combinatorics, but R is equal to two, so this is relatively efficient. This requires big O of the maximum number.

[00:14:16]Then, we have to get the number of pairs with a GCD of each index. This requires big O of the maximum number log of the maximum number. Remember that these two steps, four and two, are very similar.

[00:14:34]And here for five, we need to get the number of pairs with a GCD of five or less. Here we run a perfect sum. This requires big O of the maximum number.

[00:14:46]And finally, we need to answer queries, so this requires big O of the amount of queries times log of the maximum number.

[00:14:56]Remember that we need to run a binary search, and it requires log of M.

[00:15:01]And space complexity would be big O of the maximum number plus the amount of queries. We are using an array with a size of M, and then we need an array for the result with a size of the amount of queries. So, with all of this in mind, now let's go with the code. First, we can get the maximum value with max.

[00:15:24]And now for the first step, we need to build a frequency map or frequency array actually. This is an array with zero times the maximum value plus one.

[00:15:35]Now, we need to fill this. So, for in nums array at n plus equal one.

[00:15:42]For the next step, we need to transform the array into another one where the values are the number of elements that are divisible by the corresponding index. So, for I in range, we go from one to mx plus one.

[00:15:56]Very similar to sieve of Eratosthenes.

[00:15:59]For J in range from I times two, we start from this position. We go up to mx plus one in steps of I.

[00:16:09]And every time array I plus equal array J.

[00:16:14]Now, we need to transform the array again. Now, every element is the number of pairs with both numbers divisible by the corresponding index. So, we are using combinatorics. For I in range from one to mx plus one.

[00:16:29]There are two ways to do this. What I've showed you in the drawing was array I is equal to we can use comb in Python. The first value is n array I and the second value is r, meaning two because we're looking for pairs. This is exactly the same as array I is equal to array I times array I minus one divided by two. Okay? So, this and this up here is exactly the same. This is something that we can do when r is equal to two. When we're looking for combinations of two.

[00:17:08]Now, we need to get the number of pairs with a GCD of each index. So, we say for I in range and we go in reverse. We start from the maximum number up to zero. We are skipping index zero.

[00:17:22]Remember that this is non-inclusive in steps of minus one.

[00:17:26]Remember that it's very important to go in reverse. And once again, very similar to sieve, for shay in range from I times two to MX plus one in steps of I, array I, and this time minus equal array shay.

[00:17:44]Now, we need to get the number of pairs with a GCD of I or less for each index.

[00:17:51]So, here we run the prefix sum.

[00:17:54]For I in range, and here we say from one to MX plus one every time array I plus equal array I minus one. Okay?

[00:18:05]Now, we are ready to answer queries. So, the result is an empty array. We want to return this result, and here in between we can say for you in queries, first we need to get the index in the array.

[00:18:21]This will be the result of the current query, and for this we need to run a binary search. In Python, we can use bisect bisect left on the array using the current query plus one because remember that this is zero indexed and the array that we have is one indexed. So, we have to add one here.

[00:18:41]And we want to append to the final result, the result of the binary search, the index. So, finally we return this.

[00:18:51]So, this is the entire code. Let's submit this and see if it works.

[00:18:55]As you can see, this works and it's very efficient. I know that this is a very hard problem, so don't worry if you didn't solve it first try. If you didn't get the idea, I highly recommend you to watch this video again. Remember that repetition often helps. And if you found this useful, please drop a like, subscribe, and see you in the next one.

[00:19:16]Bye-bye.