we can also solve this problem using coin change approch .... just find max possible number which square is less or equal to n then use coins i as (i*i) range from 1 to max possible number which square is less or equal to n
Yes but that will not be the most efficient approach though, If we're on the same page, It will be a 2-d Dp solution right? But it will not throw TLE either...
Just some doubt, if we are continuously dividing n by 4 and then the resultant is getting stored in n then the for loop is being run through that "modified" value of n, which would have a different square-root value than the actual n, then why even after this modification, we are getting the correct answer!!
In the Math technique While explaining the theory you used the condition of 2 first hence it was justified to use the condition 4 next (as it is the only option left) but in the code you wrote the condition of 4 first then 2 . how is it justified?
aryan bhai i 1st wrote top-down approach it gave TLE and when I converted it to bottom up it passed all the TC and got accepted too. But as you mentioned both have the same TC and SC so how its possible?
I think no... Not every problem can be solved using theorems, But when we have a choices based problem and if we can break a bigger problem into sub problems then DP works for everything. I think, for this problem, 1D dp solution is more than enough.....
oh my god you are absolutely amazing
I remembered my 12th math class, you are amazing.
most complete channel...come up with dsa series
I'm impressed with the way you explain the problem :)
I have a feeling...you are gonna blow up on youtube very soon god bless.
yo ,your pfp is same as my phone's wallpaper...Big fan of cowboy bebop
one of the most underrated DSA channel.
keep up the good work bro!!!!
we can also solve this problem using coin change approch ....
just find max possible number which square is less or equal to n
then use coins i as (i*i) range from 1 to max possible number which square is less or equal to n
Yes but that will not be the most efficient approach though,
If we're on the same page, It will be a 2-d Dp solution right?
But it will not throw TLE either...
Awesome Explanation bro !! The math behind the theorem you explained it very well !! 👋👌✌
Nice explanation bro
Great explaination bhai. Thank you for doing beautiful work.
the only one channel wch discuss abt all the approaches
Just some doubt, if we are continuously dividing n by 4 and then the resultant is getting stored in n then the for loop is being run through that "modified" value of n, which would have a different square-root value than the actual n, then why even after this modification, we are getting the correct answer!!
these two theorem are life saver😅
wow
for checking whether it is i^2 + j^2 + k^ 2 = N, we can i and j uptill cube root of N, we can find k using i, j, N. this also works right?
thanks
In the Math technique While explaining the theory you used the condition of 2 first hence it was justified to use the condition 4 next (as it is the only option left) but in the code you wrote the condition of 4 first then 2 . how is it justified?
aryan bhai i 1st wrote top-down approach it gave TLE and when I converted it to bottom up it passed all the TC and got accepted too. But as you mentioned both have the same TC and SC so how its possible?
Was fast-paced, but nice explanation. Confused the hell out of me when you highlighted the node of 3rd depth instead of 4th.
bhaiya from where u know abt this theorem....
bro one suggestion go little slow
Use 0.75x
Does the interviewer expects us to know these theorems?
I think no...
Not every problem can be solved using theorems,
But when we have a choices based problem and if we can break a bigger problem into sub problems then DP works for everything.
I think, for this problem, 1D dp solution is more than enough.....
@@rajrajesh1669 agreed :)