2920. Maximum Points After Collecting Coins From All Nodes | Weekly Leetcode 369

[@mukultaneja7243]

Hi Mohan. Thanks for such a great explanation. Can you please confirm if 1. Dividing a positive number by 2^n, and 2. Dividing a number by 2 "n times" same or different here?

[@codingmohan]

Initially I thought it was different but I think they are same here.

[@mukultaneja7243]

@@codingmohan Yes I also verified, they are the same. So we can optimize our code further to O(N*B), I believe.

[@codingmohan]

@@mukultaneja7243 Yes we can.

[@smitrajrana4016]

@mukultaneja7243 @codingmohan is it always the case or particularly for this problem both operations are same?

[@codingmohan]

​@@smitrajrana4016 Thanks for asking. I think this is always be the case and not something to do with "2" here. Intuition - Let's say you are dividing by 2 i.e. you want to verify whether floor(N/2^X) == floor(floor(N/2)/2)... You can write N in base 2 here and you will have something like "1101.....". Here dividing by 2 and taking floor simply mean removing the last bit. Therefore if you divide further by 2, it means you are simply truncating the last 2 bits. And so on ... Further, if you divide N by 2^X, it means you are still truncating the last X bits but as it is not "floor", you will have (last X bit value)/2^X which is "always" a decimal number. And hence if you take a floor of overall, it will come as same value as the above. Replace "2" with any number of your choice and everything will still holds. Therefore, it will always be the case. A simple simulation - ideone.com/TJs2OK Let me know if you want me to create a short video on this :)

[@devenderbhatt421]

Nice approach to explain even someone new to these problems ty❤

[@sujalsingh7675]

Amazing solution

[@ani68]

At 36:50 can you please help me understand how the value of sumation Child = 2N And how does 2N is equal to the number of edges

[@codingmohan]

This is a tree which means there will be (N-1) edges. For each node we are visiting all it's neighbors. Therefore, each edge will be used twice - let's say there is an edge a --> b, then we will visit this edge when we will be at node "a" and we will visit this edge again when we will be at node "b".

[@ani68]

@@codingmohan oh yeah... got it... thanks 😊

[@ayushanand18]

after each contest, the next day I come over for upsolving. and if I do not get it within the first 40 mins, I always search the last question on your youtube. I go down until your video is there - and this is what i wait for! amazing explanation, in-depth and growth oriented. full of learning! thanks man!

[@devenderbhatt421]

At line 13 shouldn't it be zero instead of -inf?

[@AmanSingh-on4ce]

No need to run a loop to find, value of V after by_2 no of divisions. int dfs(int node,int par,int p) { if(dp[node][p]!=-1) return dp[node][p]; if(p>14) return 0; int cur = coins[node]/(1

[@RAUSHANKUMAR-gw9ri]

Hii mohan, the time complexity for brute force recursion is some what 2^n since we are calling at each index two possibilities?

[@devenderbhatt421]

U mean without dp?

[@we_atheletes]

Superb Bhaiii

[@divyanshuagarwal1912]

Nice