3164. Find the Number of Good Pairs II | Math | Factors | 3162. Find the Number of Good Pairs I

Рет қаралды 5,446

Күн бұрын

Пікірлер: 29

@ARYANMITTAL 7 ай бұрын

This can also be solved in O(1e6 log(1e6)) time, by simply using the logic which we learned in prime sieve video, by saying that for nums2[j] as 2, we look for all the multiples of it i.e. 2, 4, 6, 8, 10, ...... & same way for nums2[j] as 4, we look for multiples of 4 i.e. 4, 8, 12, .......... [for m numbers, we are going on to every number & on their multiple in this fashion which we proved in Factors & prime Factors video(link in desc) will incur a time complexity of O(1e6 log(1e6)) ]. Thus, thus for nums2[j] as the base number = b & going on to all its multiple as b+b, b+2b, b+3b, ...... We will check the count of this b + x*b value in nums1, i.e. maintain the map which will store the frequency of nums1[i] / k. And cheers you solved the problem. 🥂 3 DSA Mistakes you should never do - kzbin.info/www/bejne/e2LbaYZ7e6l-d5I

@pankajvishwakarma3124 7 ай бұрын

@ARYANMITTAL if we go on checking every element's multiples of nums2, wouldnt it give tle as in worst case time complexity is 1e5*1e6.

@hitheshpk6030 7 ай бұрын

in this sieve cannot be applied marking an index here will not help in finding right answers because if the same marked element comes once again then it should again iterate .so every element will iterate in inner loop.so tle.if i am wrong.help me in making correction. I have watched your prime numbers master class.

@namannema3349 7 ай бұрын

bhaiya i like these kind of short explanations please keep like this only 💙💙💙💙

@SmartySquad-id8ym 7 ай бұрын

A very good explaination and the efforts you are putting to explain each and every small concept is just amazing... Thanks a lot bro.. Keep it up

@dumpster-jackson 7 ай бұрын

I was not able to solve this during contest, but 8000 people solved it. Was that due to cheating or I am too dumb?

@AnilKumar-d6y1l 7 ай бұрын

us bro us

@Homelander_30 6 ай бұрын

🙂🤝

@mayankshakya9200 7 ай бұрын

Bhai aryan tumne apne time par dsa kha se seekha tha??

@study-yd6es 7 ай бұрын

Thankyou so mych bro !!

@dvalley56 7 ай бұрын

Thank you, I went thorugh the solution section but didn't wanted to read everything.

@krishpoptani7862 7 ай бұрын

Got TLE in contest 😢😢

@rajrajesh1669 7 ай бұрын

Tnx for the video

@rsKayiira 7 ай бұрын

Great video could you please provide the solution for Q4 Contest 399 using Recursion and Memoization

@Taciturn123-r6j 7 ай бұрын

Hey Aryan Jii.. How can we know which data structure sutable to use by checking constraints? By the by.. Learning so much❤ from u daily.. My utube recommendations full of urs🎉😁

@Benstokes555 7 ай бұрын

after looking at the solution, i felt the solution i quite easy(even though i didnt get it on my own), yet the submission rate is too low..

@vibhanshusharma9143 7 ай бұрын

bro take example ele=12 and 3 comes factor we add freq of 3 and (ele/factor)=4 of nums2 in ans but in next iteration the factor comes 4 and 3 so we add it again .............. whyyy

@dvalley56 7 ай бұрын

There won't be next iteration. Since f*f

@ashish3487 7 ай бұрын

Bhaiya 4th making?

@deathigniter2155 6 ай бұрын

Please someone tell me whats wrong in my code; int n = arr.size() , m = brr.size() , gp = 0; map < ll ,ll > factors; for(int i = 0; i < m; i++) factors[brr[i]]++; for(int i = 0; i < n; i++){ if(arr[i] % k != 0) continue; int x = arr[i] / k; for(int j = 1; j * j

@deathigniter2155 6 ай бұрын

here is the accepted / corrected code. ll n = arr.size() , m = brr.size() , gp = 0; map < ll ,ll > factors; for(int i = 0; i < m; i++) factors[brr[i]]++; for(int i = 0; i < n; i++){ if(arr[i] % k != 0) continue; int x = arr[i] / k; for(int j = 1; j * j

@ITACH1688 7 ай бұрын

TLE maar rha tha 🥲

@InquisitiveLittleSteps 7 ай бұрын

gives TLE: 684/687 passed def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int: f=defaultdict(int) for l in nums2: f[l]+=1 fc=0 for i in range(len(nums1)): if nums1[i]==1: if k==1: fc+=f[1] continue for j in range(1,math.ceil(math.sqrt(nums1[i]))): if nums1[i]%(j*k)==0: fc+=f[j] if nums1[i]%((nums1[i]//j)*k)==0 : fc+=f[nums1[i]//j] if math.ceil(math.sqrt(nums1[i])) - 1==1: if nums1[i]>2 and nums1[i]%2==0 and nums1[i]%((nums1[i]//2)*k)==0: fc+=f[nums1[i]//2] if math.sqrt(nums1[i])==math.ceil(math.sqrt(nums1[i])) and int(math.sqrt(nums1[i]))!=(nums1[i]//2) and nums1[i]%(math.sqrt(nums1[i]) * k)==0: fc+=f[int(math.sqrt(nums1[i]))] return fc

@ARYANMITTAL 7 ай бұрын

I couldn’t read each line due to non code formatting on phone, but i see no pruning here

@InquisitiveLittleSteps 7 ай бұрын

@@ARYANMITTAL Yes.. actually i should have used math.floor()+1 instead if ceil(). Because of this i was missing out the nums11[i]//2 number again to include that number, i had to do those big if conditions. After seeing your video, i used math.floor()+1 ensure that nums1[i] is not missed and that f1 != f2 condition is satisfied... f1 != f2 was not satisfied when ceil() was used... that's why i was getting expected+1 for every teas case... But after the changes, it has been ACCEPTED. Thank You sooo much Aryan bhai ..