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
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.
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
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.
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 :)
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
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
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.?
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
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
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 !
@@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.
Sorry for the wait... this one took a 'bit' longer than I expected 😆
Nice pun 🤣
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!
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
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.
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
Awesome explanation on the Bitmask part...Helped me visualize it.
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.
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 :)
The best coding channel on youtube
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.☺
Please do a separate video for explaining bit mask.
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.
Why code it when in just about all the major languages you have built-in functions that do it for you?
@@psibarpsi it is not that big of code and I think it would make a good impression in interview
@@psibarpsi Because I remember learning it recently😅 Also like Aryan above said, good impression👍🏻
some people get to be this awesome!
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 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])
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
wow u are life savior NEET!
Wooh that was some problem. Not easy to figure out Bit masking. thanks!
The best solution!
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
At 10:15
can you add this google question to your playlist
2184 Number of Ways to Build Sturdy Brick Wall
Thank you for everything you do!
we can cache also the gcd result if we use (1
thought you said op was redundant information?
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.?
You are a 'bit' of a genius!😂
had no idea you had this second channel. I thought you stopped leetcode because you started working
Clean as usual hats off
Great explanation
Thanks for the daily
daily savior
How do you do these drawings?
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
this video has many conceptual gaps...Explanation is not crystal clear
Is there any portion that is lacking?
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
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 !
@@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.
@@AR_7333 ohh i see, thanks
great explanation