Perfect squares | Dynamic programming | Legendre's theorem | Leetcode

[@abhijeetkumar2204]

1 hour ago I did it using dp.But I am addicted to your explanation so I came here.

[@techdose4u]

Nice :)

[@abhijeetkumar2204]

@@techdose4u can you make video on how to use leetcode for interview preparation.thank u

[@abhijeetkumar2204]

Also please make a video on how to to explain a problem in interview.

[@techdose4u]

Good idea I will make this first.

[@techdose4u]

Yea this is also good

[@AkshayKumar-xh2ob]

Your solutions are always very unique, I'm curious how you gained this knowledge. Bcoz you either know this approach or you don't. There is no way to derive or logically build it.

[@Official-tk3nc]

Tushor Roy, Back to Back SWE and Tech Dose -----------are combo pack for getting dream company

[@techdose4u]

☺️

[@watchforabhay]

There are two aspects to such problems. The logic of the problem - which is real classy here in your video, clean and simple. The other aspect being that of implementation - the crux is given -- meaning the for loop. If you could really spell out how each case connects with the code (code flow) -- that will be super awesome and will be helpful for newbies . But overall great solution and explanation. Very helpful and really thankful

[@techdose4u]

👍🏼

[@marcousosewelle5501]

Dude. If I ever make it into a top 5 tech company then I'll give you my first pay check. Serious. You are AMAZING!!!!!!!!!!

[@r3xxxx]

damn guy did you?

[@eshanprasad3594]

Its been 3years since you posted this comment, I'm curious to know did you make it?

[@hellorvce]

excellent explanation ...pls keep it up.....generally coders r not good at explaining what they code.....but u r a gem man!! hatsoff

[@techdose4u]

Thanks :)

[@mohanvamsi007]

Your explanation is so elegant make it very simple to understand the solution

[@techdose4u]

Thanks

[@Rishit.Chaudhary]

For the memoization and DP method, you can start in a greedy fashion and start with perfect squares just smaller than N every function call. Something like: for(int i = sqrt(N); i*i as i is an int type and i*i = 1024 so the next call would be min(ans, 1+solve(N-i*i)) => min(ans, 1+solve(1025-1024)) This way the recursion would get the answer faster, but we have to use the branch and bound as well to prune the state space tree so that we do not explore it completely and waste time. We use branch bound technique here where we check if we are subtracting more numbers than what the current best answer did and if so then we can stop the recursion then and there and try some other lower value instead. This way we do not explore branches that will surely not give us the optimal answer, i.e. least number of subtractions for getting N.

[@venothanand91]

Kudos to Your thought process. Clean and simple.

[@techdose4u]

😁

[@chandrakantasaini6438]

the way you explain, it is awesome. really impressive.

[@techdose4u]

Thanks

[@ArifulIslam-im7wr]

Thanks...Sir, You Always Teaching The Best Methods.

[@techdose4u]

Welcome :)

[@aakashparmar560]

Best video explanation. You got a new subscriber here.!!

[@techdose4u]

Thanks

[@radhu8]

LOL , Now I want to try only those questions on Leetcode for which you have a video! Your explanations are awesome! Please add more Medium and Hard level leetcodes!

[@techdose4u]

Haha....one day I shall cover all of leetcode 😀

[@deepaligarg2978]

Superbly explained. Thank you so much for making this video.

[@techdose4u]

Welcome :)

[@gurnoorsingh2954]

Great explanation sir Aur koi problem channel itna clear nhi samjhata

[@techdose4u]

Thanks :)

[@abhilashpatel6852]

Thank you for the explanation. This question was giving me nightmare

[@ganeshkamath89]

Is it correct to think this way? 1) If number is perfect square, it will be sum of 1 square 2) If number is a Pythogorean hypotenuse, it will be sum of 2 squares. It also need not be pythogorean hypotenuse :) 3) Otherwise if it is not of the form (4^a)*(8*b +7) then it is the sum of 3 squares 4) otherwise it is the sum of 4 squares

[@4747surya]

Can also be solved like coin change problem of leetcode least number of digits required to add up to a given number make a array from i=1 to i * I

[@Tensor08]

Bhai Mazza aa gya 🤞👌👌👌👌👌

[@techdose4u]

😊

[@awfulprogrammer619]

Keep Upload! You really helping a lot. KEEP SHINING too

[@kajalkukreja694]

Such a clear explanation. Great work 👍👍👍👍

[@sayanchowdhury3776]

sir thank you so much ,great explanation......the idea behind this is superb.....

[@techdose4u]

Welcome :)

[@alphagrowth3327]

God level explanation. Great work man 🙌

[@techdose4u]

Thanks 😊

[@SKovac]

Excellent explanation!

[@techdose4u]

Thanks ☺️

[@lokeshtech3319]

Very nice explanation

[@bookalicious9849]

Thank You ! you are the life savior of mine

[@mrityunjaygiri3397]

wonderfully explained

[@paragroy5359]

Nice explanation sir....doing a really great job thanks a lot for the video..really amazing..sir as we are using sqrt function in the for loop so don't you think the time complexity should be o(sqrt(n)*log(n))

[@avikmallick2493]

wow...the last method was amazing..just wanna know, should we know these type of theroems before or we just get to know these theroems when these type of problems arise

[@techdose4u]

Learn & apply :)

[@VinayKumar-ze2ww]

Great solution

[@kunalsoni7681]

Really very interesting and amazing session 😊☺️.. thank you sir to make daily such a helpful video 😊☺️..

[@techdose4u]

Welcome :)

[@maths_with_fun8592]

Nice explanation. Amazing

[@techdose4u]

Thanks

[@sangamsamdarshi4634]

it would help if you add chapters to your videos, btw explanation is great

[@sarahmimi5938]

Thank you so much! A real explanation!

[@chandrabhusanyadav5741]

Excellent 👍

[@amanrai9880]

Dude you never seize to amaze me!!

[@techdose4u]

😁

[@chetanpatteparapu7600]

This video is gold!

[@techdose4u]

👍🏼

[@visheshyadav2683]

Your explanation is the best bro ,keep it up❤️

[@techdose4u]

Thanks ☺️

[@AbhijeetNayak-connect]

Great videos, reduce the usage of ‘lets us say’, ‘hence’, ‘because’, ‘so’.

[@techdose4u]

That's the problem with me. I know I use many so's therefore etc. I dunno how to get rid of this 😅 Any suggestion?

[@AbhijeetNayak-connect]

@@techdose4u Practice is the only way to get rid of these filler words. You've the videos to take notes of how many times you're saying these, that will give you an idea. Then, consciously you have to suppress these word. Sounds easier said than done :)

[@oqant0424]

thanks a lotttttttttt u explained it so well🤩

[@techdose4u]

Welcome 😊

[@suhasnayak4704]

Great video! Thank you! What is the time and space complexity for recursion and memoization?

[@anmolwadali9227]

really great explanation sir

[@techdose4u]

Thanks

[@snehal462]

man your solutions are amazing!

[@techdose4u]

Thanks bro :)

[@babycoder-shantanusaha5218]

13=3*3+2*2 13=9+4 2 is the minimum

[@saravanan925]

What an explanation!!!

[@techdose4u]

Thanks :)

[@liaodaniel1684]

Excuse me Sir, are the two points at 19:57 the reasons why 13 can be used to solve the number 52? Thank you for your amazing videos!

[@optimizedvishu7754]

in line no.8 you are changing n , by dividing it by 4 , and using same value of n every where in the last code sir please explain if is it working ?

[@yitingg7942]

Your explanation is amazing!! Can you also do one for lc 91 Decode Ways please ?

[@vineetsharma4635]

What's the time complexity of recursive solution? Moreover, how to define a recurrence relation for it?

[@abhinavshukla5164]

Meomoization code cplexity is o(n)2

[@adityaagarwal1650]

bhaiya how much total time do you invest in these solutions , ranging from finding different methods to recording them nicely ? :):):) Thanks for your hard work .

[@techdose4u]

Bro...you can only know it when you see me live. It requires a lot of effort to put video for a good question :) Thanks for appreciating my efforts.

[@skystone1000]

@@techdose4u Yes, I know it takes a lot of effort to do these things, thank you for your detailed explanation

[@kimpma7380]

why we need to create the int dp [n+1] instead of dp[n] when we use the recursion with memorization? Thanks

[@garimakumari4346]

woow man..thanks

[@techdose4u]

Welcome 😀

[@crimsoncad3230]

Can you please help me with dynamic programming??? I want to know how to start with dynamic programming. Easy to Medium. Just like you do for recursion when you are discussing a easy Tree question. Do it for DP as well.

[@techdose4u]

Got it bro. Actually in geeksforgeeks, you can find under DP, problems are sorted hardness wise.

[@crimsoncad3230]

@@techdose4u Thanks bro. It was very helpful. But just when you are solving any DP problem, please mention something like these in the video: "This is a good problem to understand DP" OR "This problem might be a bit difficult for those people who are starting with DP" OR "This is an easy/intermediate/high level DP problem"

[@exodus5948]

@@crimsoncad3230 i suggest you to understand 0-1 knapsack problems. I have some standard 7-8 questions and most of the new dp questions are also an extended form of this as well.

[@JgNt3981]

Sir, How to develop probelm solving skill ?

[@nishantjawla4085]

For the method 3 bcz of while(n%4 == 0) th TC should be O(n) ?

[@SwetaKumari-uv4ul]

Please upload video on egg dropping problem dynamic programming

[@techdose4u]

Sure

[@rajatbudania6181]

very well explained :)

[@abhaysahoo7652]

sir what is the software you use for writing on the screen?

[@tusharsharma5109]

Bro i read in your recent post that you will stop this Leetcode monthly series from July , please don't your explanation of these problems are just amazing. Even if I come up with a solution of my own then too i watch your video because always i learn something new :)

[@techdose4u]

I know its painful but still I had to take this decision. It will be more helpful to teach topicwise rather than random problems :)

[@subham-raj]

I came up with the dp solutions, but the math tho :(

[@rishabhgupta7976]

make video on wildcraft matching please

[@kbhargavi4400]

Tq for ur efforts sir! 🙏🙏

[@kavitameena67]

Which tool do you use for drawing and explaining ?

[@ThePaullam328]

I'm confused about how you derived n % 8 == 7 from N / 4 ^ a = 8b + 7?

[@ridimamittal4064]

THANK YOU SIR !!

[@techdose4u]

Welcome

[@rohithkumartangudu4664]

Bro please reduce the ads. It is disturbing while watching video.

[@techdose4u]

Sure.

[@rohithkumartangudu4664]

@@techdose4u thank you

[@techdose4u]

@@rohithkumartangudu4664 DONE

[@rohithkumartangudu4664]

@@techdose4u thank you bro. Are you telugu guy??

[@techdose4u]

No 😅

[@rakshith3547]

Baap of DP!

[@techdose4u]

🙏

[@jatinthakwani5370]

Thank you so much

[@techdose4u]

Welcome

[@suharajsalim4549]

Thanks a lot!

[@techdose4u]

Welcome

[@zuojimmy1198]

thanks a lot

[@myvinbarboza3038]

Thanks :)

[@josemarcano5136]

why ans=Math.min(ans, 1 + solve(n-i*i)); //why this formula. how did you come up with this formula? how can we derive this formula in 20 mins?

[@techdose4u]

This is not a formula. I showed you, that this is a breakpoint generation. You need to create breakpoints at Perfect Square intervals. This is the entire concept in this problem.

[@abhijeetkumar2204]

@@techdose4u this question was somewhere similar to coin exchange problem

[@AkshayKumar-xh2ob]

JAVA DP tabulation solution: class Solution { public int numSquares(int n) { int dp[] = new int[n+1]; for(int i=0; i

[@techdose4u]

👍🏼

[@vikramsingla2311]

Won't this solution also work if we ignore "Time Limit Exceeded" clause shown on leetcode. public int numSquares(int n) { int count=0; while(n>=0) { int a= (int)Math.sqrt(n); count++; n=n-(a*a); } return count; }

[@DeepakKumar-nu6zo]

No see when u do it for a no like 12 in first case u reduce ur no to 3 2nd case to 2 3rd case to 1 ,,oh then wait a minute no remains 1 all the time infinite loop.......

[@vipinshanmugam3036]

i don't understand why we are taking minimum in recursive approach, someone help me! P.S: I'm not from a CS stream🙃

[@rahulagarwal8059]

👍🏻

[@techdose4u]

👍

[@srinivasakumaratmakuru293]

🎯 Key Takeaways for quick navigation: 🧮 The *video discusses solving a mathematical problem related to perfect squares and dynamic programming.* 💡 It *aims to find the number of perfect square sums that can be obtained from a given list of numbers.* 📝 Legendre's *theorem is mentioned as part of the solution strategy.* 🎯 The *goal is to achieve a minimum of 500 distinct sums.* 🤔 The *video hints at applying concepts like Indian cuisine to illustrate the problem-solving process.* 📚 It *emphasizes the importance of subscribing to the channel for more content and updates.* 🔍 The *video encourages viewers to consider various factors and strategies in problem-solving.* 📈 It *suggests that by understanding key concepts, viewers can tackle similar problems effectively.* Subscribing to *the channel is emphasized multiple times throughout the transcript.* The content *discusses various mathematical concepts, including squares, multiples, and divisibility.* There's a *mention of the importance of subscribing to receive updates and new content.* The transcript *includes some numerical examples and calculations related to mathematical problems.* Different methods *and strategies for solving problems are mentioned.* The transcript *also mentions the representation of numbers using different techniques.* It emphasizes *the importance of understanding and verifying solutions.* There are *reminders to subscribe to the channel for more content and updates.* Made with HARPA AI

[@darshantank554]

First view🥳🤗

[@techdose4u]

😁

[@manjeshsingh3002]

hadd h YAAR..koi videos dekhe ya tmhare ads?????

[@noname-ut5rw]

Bad

[@ankitMalviya152]

very good explanation

[@techdose4u]

Thanks 😊