Maximize Score after N Operations - Leetcode 1799 - Python

[@NeetCodeIO]

Sorry for the wait... this one took a 'bit' longer than I expected 😆

[@heyitsmembermark]

Nice pun 🤣

[@yooos3]

Never have I ever thought a DP problem with bitmasking would make sense in just one time explanation. Your channel is superb! Thank you for this!

[@JimmyLai-l1h]

Thanks! Couldn't have solved the problem without this video. Just like to share a little trick I saw in others' solutions for i in range(len(nums)): if mask & (1

[@MP-ny3ep]

The best coding channel on youtube

[@pradipakshar]

If anyone's confused why we have n squared choices for each operation [1, 2, 3, 4, 5, 6] In the explanation, Neet kinda missed to explain this part He was saying we have n squared choice but the way he proceed to explain looks like n choice as (1,2) or (1,3) or(1,4) and so on But in reality, we need to choose the max for each operation count, so we can choose (1,2) or (2,4), or (5,6) or anything which gives us a max gcd Thus for each operation we make n squared comparisons :)

[@arghyadas4138]

9:33 Precious Information✨✨ I made the mistake where, I used the operation number as the key because I thought that It is the only changing number, this should be the key. Thanks for telling why not to use that

[@zhewei719]

Thank you for the update! I've been waiting for your new video all day cuz I found other videos about the same problem are always not satisfying compared to yours.

[@zaki_1337]

Was waiting for this. Edit: Easy GCD function: gcd(a,b) { while( b!=0 ) { r=a%b; a=b; b=r; } return a; } Euclid's algorithm.

[@psibarpsi]

Why code it when in just about all the major languages you have built-in functions that do it for you?

[@kaushik.aryan04]

@@psibarpsi it is not that big of code and I think it would make a good impression in interview

[@zaki_1337]

@@psibarpsi Because I remember learning it recently😅 Also like Aryan above said, good impression👍🏻

[@sreekrishnak7747]

class Solution: def maxScore(self, nums: List[int]) -> int: n = len(nums) @lru_cache(None) def dfs(k,avail): if k == half_n + 1: return 0 maxi = 0 for i in range(n): if avail & (1

[@rithickchowdhury7116]

Awesome explanation on the Bitmask part...Helped me visualize it.

[@akanksha1441]

I was going to skip today's challenge because the solution on leetcode looked so difficult. Thanks for what you do, you make learning so simple.☺

[@rhugvedbhojane4387]

Hey NeetCode! Thank you for the great explanation and for introducing a new concept to me. I really learn a lot from you. Keep up the good work by educating us.

[@GameFlife]

wow u are life savior NEET!

[@kingKabali]

Please do a separate video for explaining bit mask.

[@StellasAdi18]

Wooh that was some problem. Not easy to figure out Bit masking. thanks!

[@aditijain2448]

some people get to be this awesome!

[@keshavkunal2195]

You are a 'bit' of a genius!😂

[@thecruio]

I have this error I don't know why? Please help AttributeError: 'module' object has no attribute 'gcd' score = op * math.gcd(nums[i], nums[j])

[@JustTrace17]

Thank you for everything you do!

[@techmoon_]

The best solution!

[@Mind_Mechanics_]

Clean as usual hats off

[@sanis85]

we can cache also the gcd result if we use (1

[@chandrachurmukherjeejucse5816]

Great explanation

[@kartikeyrana3736]

can someone help me know what the problem with my solution is ? 1 -> sort the array nums then take the last element(the biggest) and look for the second biggest such that their remainder == 0 and take their gcd and store this gcd in an array 2 -> for the remaining pairs take their GCD as 1 3 -> now sort the GCD array, multiply the largest with n then the second largest with n-1 and so on and as for those remaining pairs we had earlier, add one for each pair this gives me 80% correct answer and fails for some big test cases

[@MohammedShaikh-h7t]

Shouldn't the inner loop j be in range from 1st to last element as well and not from i+1 as the even though the pair may get computed again but its order is important as well to maximise as op is considered.?

[@uptwist2260]

Thanks for the daily

[@yichensun6973]

daily savior

[@azgharkhan4498]

I think we should not have cached the score with operation multiplied. Because as an example I can pick 5,6 in operation 2 as well

[@azgharkhan4498]

At 10:15

[@aishwariyaaish8305]

can you add this google question to your playlist 2184 Number of Ways to Build Sturdy Brick Wall

[@DevvOscar]

How do you do these drawings?

[@CS_n00b]

thought you said op was redundant information?

[@vikneshcs4824]

Why here backtracking the changes in bitmask is not needed

[@PRANAVMAPPOLI]

Why this method doesnt work ? class Solution: def maxScore(self, nums: List[int]) -> int: heap=[] numDict=Counter(nums) n2=len(nums) n=n2//2 for i in range(n2): for j in range(i+1,n2): heapq.heappush(heap,(-math.gcd(nums[i],nums[j]),nums[i],nums[j])) res=0 while(heap and n): gcd,num1,num2=heapq.heappop(heap) if not numDict[num1] or not numDict[num2]: continue numDict[num1]-=1 numDict[num2]-=1 res+=-gcd*n n-=1 return res

[@codetrooper9279]

this video has many conceptual gaps...Explanation is not crystal clear

[@NeetCodeIO]

Is there any portion that is lacking?

[@AR_7333]

tried a greedy approach. Idea being we have to use the largest gcd for the nth operation. Step 1: compute GCD for all combination of 2n nums. Push into a heap along with the index of nums for which the GCD was calculated. Step 2: Pop from the heap and keep track of the indices which were already used in the result calculation. Repeat step 2 until all the indices have been used. finally return the result. It failed for this test case: [109497,983516,698308,409009,310455,528595,524079,18036,341150,641864,913962,421869,943382,295019] expected: 527 actual output: 525 Not sure where the bug is in my code. from typing import List import heapq class Solution: def maxScore(self, nums: List[int]) -> int: def gcd(a, b): while b: a, b = b, a % b return a max_heap = [] len_nums = len(nums) for i in range(len_nums): for j in range(i+1,len_nums): val = gcd(nums[i],nums[j]) heapq.heappush(max_heap, (-val,(i,j))) ans = 0 seen_nums = set() for i in range((len_nums//2),0,-1): while True: val = heapq.heappop(max_heap) gcd_val = -val[0] n1,n2 = val[1][0],val[1][1] if n1 in seen_nums or n2 in seen_nums: continue else: seen_nums.add(n1) seen_nums.add(n2) break ans = ans + (i*gcd_val) return ans

[@kartikeyrana3736]

i too used somewhat same approach and it works for like 80% of the test cases, i wonder what the problem is with this approach. if you find out please let me know !

[@AR_7333]

@@kartikeyrana3736 When there are multiple pairs that gives the same GCD, we cannot blindly pick any pair. We need to pick a pair such that we maximize the GCD for the nums there were not picked.

[@kartikeyrana3736]

@@AR_7333 ohh i see, thanks

[@vishalbhardwaj8577]

great explanation