Count the Number of Square-Free Subsets | Weekly Contest 333 | Leetcode

[@TrueSolutionsOfficial]

very good bro again , subscribed today

[@rishabprasad5593]

Good job! Very lucid explanation with underlying basics needed. 👍

[@bhargav1811]

14:21 isn't 5 also square free number? 11:39 wouldn't be time complexity be 2^n because for every index of array we are checking whether to include or not to achieve the given sum !! why just N *10?? 13:08 how had we reduced the 2^n into order N means? the overall complexity would be equal to O(O(N* 10 ) *10 ) which can be like approx O(N^3) ? correct me if i am wrong?

[@tarunpatel8168]

Thanks bhai for great intuition building

[@kapilchoudhary2922]

Brilliant explanation!!

[@samagrapathak3854]

great solution

[@amankrsingh]

Please upload 2nd one also using recursive approach

[@codingmohan]

I solved 2nd using Dijkstra (seems like overkill) but I'm still not able to understand the "complete" proof of the recursive approach. Let me know if you would like to know about the Dijkstra approach.

[@amankrsingh]

@@codingmohan yes please upload 2nd one And if it seems to be very tough then please increase the video length so that we can easily understand the concepts

[@codingmohan]

Here you go - kzbin.info/www/bejne/ZpmnZZ-Im7BghbM

[@shivanshsingh176]

Thank u so much

[@doingit621]

plz post the dijkstra solution of 2nd question.

[@codingmohan]

Here you go - kzbin.info/www/bejne/ZpmnZZ-Im7BghbM

[@doingit621]

@@codingmohan sir can u plz share ur linked in

[@doingit621]

@@codingmohan ur explanations are top notch

[@doingit621]

can you plz explain 2nd question using the recursion/dp approach. Why do we always to to the nearst power of 2??

[@dawodujohnson]

Very nice. Any tip on how to think this way during contest ? where do you practice ?

[@codingmohan]

This may help - kzbin.infoUgkxQl3X9x7nzPsycq35BZE5dpxvrrC4ovvH

[@souravshaw8904]

Nice explanation 💯

[@krishankant3720]

Thank u sir 4 uploading video

[@nideeshn6293]

Can you make a video for 2nd question as well

[@codingmohan]

I solved 2nd using Dijkstra (seems like overkill) but I'm still not able to understand the "complete" proof of the recursive approach. Let me know if you would like to know about the Dijkstra approach.

[@AakashKumar-vf3dh]

I didn't understand why this wouldn't give TLE as the TC is 1e9. Can you explain why this would pass?

[@codingmohan]

TC is not 1e9. It's 1e6. We are calling recursion everytime in the loop "but" we already considered the complexity of "all" possible recursion calls with 1e6 states. Think of it like this - call recursion for every single state "before" the loop and then you'll have everything in your "dp" populated. Now when you call it inside a loop, everything you'll get from the dp array itself i.e. O(1).

[@pwnweb5734]

how do i reward .. there is no option to pay in this video. would love to reward what i can for the good work

[@codingmohan]

Thank you for your kind words. Glad you find it helpful :)

[@iWontFakeIt]

🔥