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 - ruclips.net/video/E1x8SEFDKA0/видео.html
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.
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🎉😁
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
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
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
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]))]
@@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 ..
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 - ruclips.net/video/E1x8SEFDKA0/видео.html
@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.
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.
bhaiya i like these kind of short explanations please keep like this only 💙💙💙💙
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
Thank you, I went thorugh the solution section but didn't wanted to read everything.
Thankyou so mych bro !!
Great video could you please provide the solution for Q4 Contest 399 using Recursion and Memoization
Bhai aryan tumne apne time par dsa kha se seekha tha??
Tnx for the video
I was not able to solve this during contest, but 8000 people solved it. Was that due to cheating or I am too dumb?
us bro us
🙂🤝
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..
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🎉😁
Got TLE in contest 😢😢
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
There won't be next iteration.
Since f*f
Bhaiya 4th making?
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
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
TLE maar rha tha 🥲
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
I couldn’t read each line due to non code formatting on phone, but i see no pruning here
@@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 ..
got TLE on testcase 682 / 687 🥲
ye tle me partial score milta hai contest ke time ?
@@YouAreHacked69 no
@@dumpster-jackson mereko kyun tag kar Diya