Maximize Score after N Operations - Leetcode 1799 - Python

Solving leetcode 1799, maximize score after N operations. Today's daily leetcode problem on May 13th.

0:00 - Understand problem
3:55 - Brute force explanation
5:25 - Memoization explanation
10:35 - Time Complexity
11:35 - Coding solution

leetcode 1799

#neetcode #leetcode #python

[NeetCodeIO]

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

[yooos]

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-lh]

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<<i): continue
for j in range(i+1, len(nums)):
if mask & (1<<j): continue

It can speed up a little 'bit'

[ashkan.arabim]

lol I was gonna comment what an inefficient solution you have (I was gonna find all gcds, store them in a heap, pop the largest one, then decrement the coefficient until the heap is exhausted), but then I came to test case 68 and realized how wise you are :p

[arghyadas]

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

[zhewei]

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.

[rithickchowdhury]

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

[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 :)

[kingKabali]

Please do a separate video for explaining bit mask.

[akanksha]

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.☺

[rhugvedbhojane]

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.

[zaki_]

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.

[sreekrishnak]

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 << i):
continue
for j in range(i+1, n):
if avail & (1 << j):
continue
maxi = max(k * gcd(nums[i], nums[j]) + dfs(k+1, avail | (1 << j) | (1 << i)), maxi)
return maxi

half_n = n // 2
return dfs(1, 0)

[StellasAdi]

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

[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])

[keshavkunal]

You are a 'bit' of a genius!😂

[kartikeyrana]

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-ht]

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.?

[CS_nb]

thought you said op was redundant information?

[aishwariyaaish]

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