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

This video explains an important programming interview problem which is to find the minimum number of sqaures which can be added to form a given
number N.We can solve this problem by various methods but the simple recursive method will take exponential time.I have shown 3 methods to solve
this problem.The first method is by using recursion with memoization to remove unnecessary recursion calls.The second method is by using Dynamic Programming tabulation method.The third method is based on Legendre's 3-square theorem.This method gives the best time complexity of just O(sqrt(N)).At the end of the video, i have shown the code walk-through.
CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
=================================================================
CODE LINK: gist.github.co...

[@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

[@Official-tk3nc]

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

[@techdose4u]

☺️

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

[@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?

[@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.

[@Tensor08]

Bhai Mazza aa gya 🤞👌👌👌👌👌

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

👍🏼

[@aakashparmar560]

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

[@techdose4u]

Thanks

[@mohanvamsi007]

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

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

[@awfulprogrammer619]

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

[@gurnoorsingh2954]

Great explanation sir Aur koi problem channel itna clear nhi samjhata

[@techdose4u]

Thanks :)

[@venothanand91]

Kudos to Your thought process. Clean and simple.

[@techdose4u]

😁

[@alphagrowth3327]

God level explanation. Great work man 🙌

[@techdose4u]

Thanks 😊

[@SKovac]

Excellent explanation!

[@techdose4u]

Thanks ☺️

[@chandrabhusanyadav5741]

Excellent 👍

[@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

[@chandrakantasaini6438]

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

[@techdose4u]

Thanks

[@oqant0424]

thanks a lotttttttttt u explained it so well🤩

[@techdose4u]

Welcome 😊

[@ArifulIslam-im7wr]

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

[@techdose4u]

Welcome :)

[@bookalicious9849]

Thank You ! you are the life savior of mine

[@lokeshtech3319]

Very nice explanation

[@abhilashpatel6852]

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

[@VinayKumar-ze2ww]

Great solution

[@chetanpatteparapu7600]

This video is gold!

[@techdose4u]

👍🏼

[@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

[@mrityunjaygiri3397]

wonderfully explained

[@kajalkukreja694]

Such a clear explanation. Great work 👍👍👍👍

[@sarahmimi5938]

Thank you so much! A real explanation!

[@maths_with_fun8592]

Nice explanation. Amazing

[@techdose4u]

Thanks

[@visheshyadav2683]

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

[@techdose4u]

Thanks ☺️

[@sayanchowdhury3776]

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

[@techdose4u]

Welcome :)

[@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.

[@garimakumari4346]

woow man..thanks

[@techdose4u]

Welcome 😀

[@amanrai9880]

Dude you never seize to amaze me!!

[@techdose4u]

😁

[@saravanan925]

What an explanation!!!

[@techdose4u]

Thanks :)

[@kunalsoni7681]

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

[@techdose4u]

Welcome :)

[@sangamsamdarshi4634]

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

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

[@snehal462]

man your solutions are amazing!

[@techdose4u]

Thanks bro :)

[@anmolwadali9227]

really great explanation sir

[@techdose4u]

Thanks

[@suharajsalim4549]

Thanks a lot!

[@techdose4u]

Welcome

[@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!

[@rajatbudania6181]

very well explained :)

[@kbhargavi4400]

Tq for ur efforts sir! 🙏🙏

[@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

[@ridimamittal4064]

THANK YOU SIR !!

[@techdose4u]

Welcome

[@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

[@TheBatterHalf]

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

[@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 ?

[@jatinthakwani5370]

Thank you so much

[@techdose4u]

Welcome

[@abhaysahoo7652]

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

[@rakshith3547]

Baap of DP!

[@techdose4u]

🙏

[@zuojimmy1198]

thanks a lot

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

[@yitingg7942]

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

[@JgNt3981]

Sir, How to develop probelm solving skill ?

[@myvinbarboza3038]

Thanks :)

[@nishantjawla4085]

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

[@kimpma7380]

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

[@babycoder-shantanusaha5218]

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

[@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.

[@kavitameena67]

Which tool do you use for drawing and explaining ?

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

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

👍🏼

[@ThePaullam328]

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

[@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

[@SwetaKumari-uv4ul]

Please upload video on egg dropping problem dynamic programming

[@techdose4u]

Sure

[@darshantank554]

First view🥳🤗

[@techdose4u]

😁

[@rishabhgupta7976]

make video on wildcraft matching please

[@rahulagarwal8059]

👍🏻

[@techdose4u]

👍

[@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 😅

[@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

[@subham-raj]

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

[@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🙃

[@manjeshsingh3002]

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

[@noname-ut5rw]

Bad

[@ankitMalviya152]

very good explanation

[@techdose4u]

Thanks 😊