Leetcode Daily . Sorted GCD Pair Queries

[00:00:01]Hey all uh let's solve today's lead code daily which says sorted GCD pair queries.

[00:00:12]I haven't solved it before.

[00:00:15]Let me reset the timer and start uh reading the problem. Let's see how we can approach it.

[00:00:24]Given an integer array nums lengthen integer array queries.

[00:00:31]GCD pairs denote array calculating pairs for all the nums of I and nums of J. I less than J and then sorting these values in ascending order.

[00:00:48]We are given queries. We need to find element that queries of five in gcdps.

[00:00:58]Got it?

[00:00:59]And we need to return that array answer.

[00:01:04]Answer is the value at GCD pairs of query of okay.

[00:01:15]What are the constraints?

[00:01:18]* length 10^ 5 of 5 into 10^ 4 of can be up to n into n - think about Good job. So, Yeah.

[00:02:20]So let me explain the problem first. We are given an arrays and we are have having some queries and for every pair I comma J pair I less than J. Now in nums we need to find the GCD.

[00:02:42]Now once we get the GCD we need to sort them.

[00:02:50]After sorting we need to uh we are having some queries and we need to get the value of uh sorted gcd at the query index.

[00:03:05]So we are having suppose from SAS three and four.

[00:03:27]We find GCD for all the nums.

[00:03:32]uh gcd of 2a 3 is 1. GCD of 2a 4 is 2.

[00:03:38]GCD of 3a 4 is 5. Now we sort this gcd array 1a 1a 2 and H once we sort we are having some queries.

[00:04:08]So we need to find GCD at queries of five.

[00:04:13]For uh query zero the output would be one. For query one output would be one.

[00:04:19]For query two output would be two.

[00:04:24]So answer would be 1 comma 1 comma 2. So for the given there is 32 should be two.

[00:04:39]That's all we focus on how to find smallest GCD at every query.

[00:05:07]Suppose if we are given query two we need to find second smallest GCD in the given array.

[00:05:25]So now what would be the brute force approach you can think of?

[00:05:30]Uh when you see all the I comma J you would think of generating all the pairs and find the GCD push back GCD for all the pairs and then sort the GCD and get answer for every query and return that answer array.

[00:05:55]Right?

[00:05:57]Now what would be the complexity?

[00:06:02]Suppose for the given n it is still 10^ 5 and queries are still n into n - 1 by 2.

[00:06:14]So if we take 10^ 5 10^ 5 into 10^ 5 - 1 by 2 it is uh into billions it is not uh optimal.

[00:06:31]So we need to forget about uh computing gcd for every pair and sorting it.

[00:06:41]So uh now just to understand like what is uh where is the optimization we can make currently we are uh what we are doing we are uh creating pairs we are going to each pair in the nums and then generating gcd then we are sorting and finding it.

[00:07:15]So the issue is not finding the GCD but generating in a pairs.

[00:07:23]So do we need to check each and every pair suppose uh there is a repetitive2 array.

[00:07:35]Suppose we have 4a 4. GCD of 4a 2 4a 1 4a 2 4a 1 is always same.

[00:07:57]So instead of uh finding GCD for all the pairs uh can't we create a frequency map and find GCD for all the pairs in the frequency map? So we just need all the possible GCDs in the array ID. So 4a 2 4a 1 4a 2 4a 1 this is a repetitive pattern which does not even make sense and gcd of 4a 4 is four itself.

[00:08:35]So there is uh no point of calculating gcd for the rep elements. So let me create map of the given nums.

[00:08:55]Now this will be reduced to commun.

[00:09:06]Yeah.

[00:09:08]Now this is enough. Now instead of generating pairs uh can we simply know that how many pairs have GCD1 how many pairs have GCD2 so on uh if it is possible we don't need to make a huge array so let me think in the terms So for every possible GCD I need to find how many pairs uh can give that GCD.

[00:09:58]This feels strange.

[00:10:01]Can we I feel that both will give exact uh the same information. But what would be the final output array is the question.

[00:10:40]Let me take a sorted area first. 1 25.

[00:10:50]Yeah. Now I have uh repetitive ones and twos. Now if I find GCD it is the same one 1 1 1 2 5 uh if I store the GCD count it would look like this 1 is 2 2 is 2 * 5 is one time in this way we can store the count and in ascending manner ascending living order panel instead of having entire array of answer for GCP.

[00:11:35]So let me check uh what would be complexity of this.

[00:11:44]Suppose uh it is still 10^ 5 and possible values are still from 1 to 10^ 5.

[00:12:02]Now we are having map. It is off in operation. In the worst case we are not doing any sorting.

[00:12:14]So uh it would be 10^ five operations.

[00:12:22]Yeah, this is this satisfies the given constraints.

[00:12:30]Uh can I think of any better approach or shall we proceed with this?

[00:12:46]Now we are knowing that how many pairs have GCD 5, GCD2, GCD 1.

[00:12:59]Can we count them without looking every pair?

[00:13:13]We know that how many pairs have GCD K.

[00:13:18]Uh we instead of taking every pair to compute GCD.

[00:13:28]Let me think of better approach here.

[00:14:04]I'm trying to think in terms of divisibility if like I have 12 and 18 both are divisible by 6 GCD 6.

[00:14:17]So until uh all the numbers are not divisible are not divisible by six.

[00:14:28]So uh uh we can get all the numbers which will visible by six.

[00:14:40]Uh so their count suppose I have uh 6 12 18 24.

[00:14:56]I have four numbers which are divisible by six. Now to get gcd6 I need to take pairs any two pairs of this.

[00:15:10]So what would be the case?

[00:15:17]Uh uh uh we need to choose two numbers from this 4 Z2. We can do combination.

[00:15:33]Wait. Ah but GCD of 6, 12 is not six. It is three.

[00:15:46]Right.

[00:15:48]I missed this.

[00:15:58]It is easy to count in this div but the GCD is not exactly the same uh lowest divisor.

[00:16:10]It might vary. So you need to understand key difference.

[00:16:32]TCD would be 12 for 12 and 24. base.

[00:16:43]Uh oh yes.

[00:17:01]Now suppose uh yeah I understood the problem. Now I have GCD 12 24 uh 18 so on.

[00:17:14]Now for the given pair uh I take I take any pair in this. Now to get the GCD we need to know we need to include that element or exclude that element.

[00:17:30]we can't generate all the pairs and we can't count how many pairs has this. So we need to know whether we need to include [clears throat] it or exclude it to get the given GCD.

[00:17:46]Uh so this is the efficient way.

[00:17:57]So uh we can uh try reversive and inclusion occlusion for that. Uh I'm thinking I'm just thinking in terms like if I need uh k smallest or largest uh can I count how many answers will be equals to value mean instead of generating all the gcds how many answers will be equals to the gcd There you go.

[00:18:52]Right.

[00:19:00]So number of pairs are n into n minus 1 by 2. This will be happening for everything.

[00:19:10]So six has uh four uh divisible values. So number of things will be 4 into 4 - 1 by 2 which is 6.

[00:19:25]Huh?

[00:19:27]This makes sense. Now why should we consider multiples is because like if I take 6 and 12 they both are still divisible by uh 2 and 3.

[00:19:48]So it gets counted with two also.

[00:19:52]Suppose two uh I take 48 the GCD is four. But now if I take 2, 6, the GCD is two.

[00:20:05]Uh now our count contains uh GCD can be 2 4 6 and 8.

[00:20:13]Now if I want to remove that extra base.

[00:20:18]Now for all the things which are divisible by two towards right we find uh so in this way I think uh it is let me What's the right approach?

[00:20:52]So we travel all elements from uh max what can the GCD be from 1 to max value.

[00:21:22]So we traverse from one to max.

[00:21:32]What happens?

[00:21:34]Suppose if G I I want GCDS2.

[00:21:43]We Oh, right, right. We can't find the GCD of the multiples of two. uh we need to traverse from right to left in that case.

[00:21:56]Makes sense.

[00:22:00]Now if I move backward I'll be having GCD of all the divisor. So I can subtract them.

[00:22:07]H now to find GCD of two you need to do GCD of 2 minus GCD of multiples of two. This is simple inclusion exclusion principle.

[00:22:30]Yeah.

[00:22:37]This is the algorithm. Let me assess complexity for this.

[00:23:11]We are it.

[00:23:40]What is the complexity of this?

[00:23:46]After finding GCD, we find the cons inclusion exclusion.

[00:23:53]But we should also need Wait. Uh I think I'm missing something here.

[00:24:11]We got all the GCDs.

[00:24:17]Now I need to build a sorted array instead of building sorted array.

[00:24:25]Why can't have uh why I can't have a prefix count?

[00:24:32]Suppose uh uh uh uh after this I might get some GC array like 1 comma 1 comma 2A 2a 5. Instead of like doing a sorted array, I can instead store this CD as 1 comma 2 1 M [snorts] got it.

[00:25:25]I get all the GCD pairs.

[00:25:29]I can have that index for the GCD pairs and I can find the next possible GCD pair by doing binary search.

[00:25:43]Oh yeah, that makes sense. Now the complexity is we find all the gcds which takes uh of M. M is the maximum value and to do binary search to find next possible uh there we do we need of login I think it's the most optimal way is there any other way let me think this is interesting Actually no I don't think there is no other optimal way. So first uh let me find maximum value element of store begin.

[00:27:00]I got sorted array. I need frequency array of values are long. Let me take long one.

[00:27:12]Let's see zero h.

[00:27:21]No, I'll do frequency map in nums.

[00:27:29]uh frequency of num++.

[00:27:36]I have frequency map. Now next what I need to do I need to traverse from right to left for in g = to max greater than or = 0 - yeah I traverse towards left oh g can't be zero it must be one like one is the maximum minimum GCD that we get. Yeah, sorry.

[00:28:12]Now, now I need to get count for each pair.

[00:28:19]Let me take zero.

[00:28:22]And now I need to get all the devices for current G and while K less than max K plus equals to G.

[00:28:48]all the devices count plus equals to frequency of okay.

[00:29:00]So I got count of all devices.

[00:29:09]No total pairs possible. Oh, we need one more array here to check inclusion.

[00:29:15]Exclusion exclude of MX + 1 comma 0 I'm thinking it has bounds. There might be values less than this but in the worst case it can be t + mx + 1.

[00:29:57]Now exclusion exclusion of current g will be equals to count star count minus 1 by 2 Wait. Uh, I took in long.

[00:30:21]Yeah, now it makes sense.

[00:30:27]Now I need to do I need to compute uh prefix counts, right? Yeah, I need to do cumulative count vector of long long prefix and I need to get value set prefix values again I need to traverse from left to right now because I'm doing prefix previously I'm doing exclusion so I try from right to left.

[00:31:17]If inclusion exclusion of G is greater than zero, now we are having pairs.

[00:31:25]Uh I need some sum is zero long long.

[00:31:36]Now I add the inclusion exclusion to prefix sum inclusion expression of G.

[00:31:48]Now prefix dot push back of some and values dot pushore uh uh tag of g makes sense.

[00:32:14]Now the only thing I need to worry about getting for each query.

[00:32:26]Sorry, it's early in the morning. So I'm feeling some discomfort to ride the boat. Let's go.

[00:32:42]Uh uh uh uh long long quil inquiries I somehow like this problem very much it feels lot of clear intuition I don't know prefix X on top.

[00:33:19]What should be the value?

[00:33:22]Where should I need index. So I'll go with I think uh this makes sense. I just push back the value add index index and I got this. I just return the result.

[00:34:17]Let me check the answer. One second.

[00:34:24]Max frequency max.

[00:34:42]What is the I to karma here? Not Same here.

[00:34:54]Lot of syntax issues.

[00:35:02]Oh man.

[00:35:11]Oh my god.

[00:35:21]That's why we need a good sleep after lot.

[00:35:33]What is name is simply Wait, I'm not excluding it. I'm just including K equals to start G.

[00:36:17]Okay. supposed to change x of g = to x of k. Now I excluded all the multiples. Now I think it would be right answer.

[00:36:39]Let me submit this.

[00:36:45]Yeah, this worked.

[00:36:49]So basically uh in a simple terms instead of finding all the pairs which is uh of square we just optimized it to keep it to 100 by focusing on divisibility.

[00:37:09]The only thing I think we need to think here is do we need to count by value instead of pair and this we will see when inclusion exclusion would be coming by practice and it's a great understanding why we need to include and exclude.

[00:37:35]Bye.