Arranging Coins - Leetcode 441 - Python

[@weaponkid1121]

I think a lot of people would love if you made a video on your process for solving a problem you haven't seen before. How long do you spend on a problem, what do you do when you get stuck, how much do you create your own solution vs read other solutions and digest them, etc. In one of your videos you said you're not some leetcode god, but you definitely come across that way, and I think seeing your process from start to finish would be really motivating!

[@mearaftadewos8508]

That would be nice. We can learn how to learn if we find a different way than ours.

[@_7__716]

Def

[@Terracraft321]

Clement

[@YT.Nikolay]

Neet, we need such series, time to make an account on twitch

[@VishalTyagi-z5n]

i did it in O(1) by using the formula i(i+1)//2= n of n natural numbers, then find out the one positive(real) root (by the fomula (-b+(underroot(-b+4ac))//2a) and return int(root)

[@reisturm9296]

Hey NeetCode, just wanted to say thank you! I received an offer to Google and couldn't be more excited. I watched your videos as a way to passively ingest some knowledge and it helped tremendously since the last time I was job hunting out of school. Cheers :)

[@mearaftadewos8508]

Hey Rei, Congrats my bro!! I have interviews at google and amazon paralley. Can you please recommend me some focus areas for google and pretty much everything you noticed and how you have prepared and for which level? Thanks in advance!

[@reisturm9296]

@@mearaftadewos8508 thanks! I wouldn't say there is a specific topic you should focus on. you can focus on your weak areas if you think you are not particularly good at a topic like DP etc. The stronger your fundamentals, the more ideas you can suggest to the interviewer and you can work with them to make your way to the solution. As your fundamentals grow, you will begin to recognize patterns and what DS/algo you can apply to the problem while working out minor details/edge cases. Good luck! Don't be down about leetcoding. It's easy to feel dumb when you cannot solve a problem. Spend some time on the problem, if you can't solve, then read the solution and try to understand it so you know why they approached it this way and take it forward.

[@mearaftadewos8508]

@@reisturm9296 Awesome. Thank you!

[@oatmeal979]

@@mearaftadewos8508 bit late but how'd the interviews go?

[@deepakff7498]

hi bro..how much time you invested to become pro in solving leetcode

[@shrimpo6416]

Just wanna thank you man... Just got my offer all bc of YOU!

[@baap6886]

you can solve it like this too: s=0 for i in range(1,n+1): s+=i if s>n: return i-1 return i

[@sankhadip_roy]

when you said u consider it as a medium level problem , I got relieved.

[@mearaftadewos8508]

The approach that came to my mind was this. Please test it and let me know if it has bugs for certain test inputs def buildstairs(tiles): row = 0 i = 1 while i < tiles: row += 1 i += row print(i, row) return row if abs(tiles - i) == 0 else row - 1 print('stairs: ',buildstairs(9)) # from math import sqrt, floor # return floor(-.5 + sqrt(1+2*tiles)) # works too

[@LiveType]

I feel smugly accomplished that my many years of math classes allowed me to almost instantly do (-1+ sqrt(1+8*n)))/2 rounded down solve this problem.

[@yuhuipang93]

Nice solution! but you don't need the "res" variable. we can just return "r", since it's the upper bound for the most rows we can complete

[@maamounhajnajeeb209]

There is no need to use max(). I try this solution and it works on leet code with over 1300 test case. the solution: class Solution: def arrangeCoins(self, n : int): start, end = 0, n while start n: end = mid-1 elif guess

[@sushantrocks]

Return the positive root of the quadratic eqn: k(k+1)/2 = n return int(math.sqrt(1+8*n)-1)//2

[@arjunreddy2647]

W

[@vgsuresh]

well you described very easily the formula for sum of first n natural numbers much more intuitively than my maths teacher... thanks much for all the work you put in these videos, helps a lot.

[@pabloarkadiuszkalemba7415]

I think you don't need to use Gauss formula to solve this. You use a semi-square, so te elements until that value will be row*col/2 and because its not a Perfect semi-square you need to add the stair (row/2). So the formula to get the values is (row*2+col)/2. And with that you can binarny search

[@augustshen8018]

in Line 13, res = mid will be enough, cuz the next possible mid will always be larger than res.

[@durgaprasadreddypeddireddy8740]

yes, that is what I was thinking too.

[@dewamscvbvx]

I was able to do this by using binary search + fibonacci sequence, with terms(i.e the number of times you iterate the fib) being the rows but It breaks down on very large integers and computing the fib sequence is VERY expensive. Although my solution is not perfect but I'm still proud considering I came up with the solution myself.

[@mearaftadewos8508]

Thank you dear NeetCode. My fav channel.

[@akhma102]

Simply the Best! I have no words!

[@harshavardhanveerannanaval8605]

A cleaner easy to understand solution, def arrangeCoins(self, n): """ :type n: int :rtype: int """ def getCoins(stairs): return(stairs*(stairs+1)/2) l=0 r=n ans=None while(l

[@Chirayu19]

Hey @NeetCode, I think the time complexity of the brute force soution should be sqrt(N) instead of O(n) since the loop is starting at 1 and will not go upto N. It will go upto Please do correct me if I am wrong. Thanks!

[@yfjsdgzjdnfn]

Same thoughts

[@ilihaspatel399]

the formula you are talking about is sum of n natural numbers which is taught in class 5 but still I appreciate the way you use the formula in binary search ... Thanks for the Solution

[@cc-to2jn]

Man i cant appriciate you enough!

[@mohamedhesham6008]

Very clear and great explanation thank you. you have the gift of teaching

[@Y1Rayn]

my issue with binary search problems is that for the while loop I never know whether to use l < r or l

[@practicefirsttheorylater]

hi, i am not that good but this is how i think about it. take just n = 1, so our left = right = 1 when we start. so if we used condition l < r, we will never check the array. thus, we must use l

[@poonamgulwane6734]

This can also work : def arrangeCoins(self, n): """ :type n: int :rtype: int """ row = 0 i = 0 while n > 0: if n >= (i + 1): row += 1 n = n - (i + 1) i += 1 return row

[@abhinowyt8564]

Hey Neetcode, how much time do you spend coding practice in a day? Before job and now

[@AppleDeuceTTV]

I do appreciate the complexity of the Gauss solution, but it made my brain hurt. The brute force is still O(log n): class Solution: def arrangeCoins(self, n: int) -> int: count = n stairs = 1 while count >= stairs: count = count - stairs stairs += 1 return stairs - 1

[@He_ze]

I originally tried doing this with prefix sum + binary search. I got memory limit exceeded, but it looked like i was kinda on the right approach

[@pojunechen2617]

Just wanted to let you know your code doesn't pass the test cases. Line 8 should be changed to mid*(mid+1)/2

[@call_me_lazarus]

Is there a typo somewhere in this solution? I've been breaking it down, and comparing it with what I have typed up, but I keep getting a few failed test cases.

[@indonline]

O(1) algo comes to mind immediately including the rounding part ....

[@ayoubalem865]

Hi neetcode here is a simple solution: return int(((0.25 + 2 * n) ** 0.5) - 1/2) Actually 1 + 2 + 3 + 4 ... n = n (n + 1) / 2 is a serie where n is equal to the last term of our serie and also represents the number of terms so all we need is just solve the equation n = i*(i + 1)/2

[@frankribery3362]

My thoughts exactly

[@duanqichuzudefangwu]

was going to say: there is a direct analytical solution

[@ChandraShekhar-by3cd]

Thanks a lot for such a great and clear explanation! How is things going at Google?

[@MrArpit1234]

n(n+1)/2 is summ of all natural numbers, which is nothing but AP, basic class 7 mathematics

[@oreoshake6287]

Isn't the Tim complexity of the 1st method so log(n)?as we are exiting from the loop when the number of coins becomes negative

[@rupambasu9722]

Hi, I really like ur problem solving approach. Can you please solve account merge problem

[@santysayantan]

I don't understand why you didn't implement the math solution? Breaking that quadratic equation would make it R = -1 + sqrt(1 + 4.2.n))/2 - > quadratic equation. Basically if we can write return (1 + int((1 + 8*n)**(1/2))/2) That would directly solve the problem. I think it says easy because it is school grade mathematics.

[@mearaftadewos8508]

I thougth of that tho.

[@oreoshake6287]

Can you please explain how you derived the formula

[@rahulprasad2318]

U can calculate it in O(1) N = floor(-.5 + sqft(1+2n))

[@JJKK-nj1vb]

sqrt is logn

[@rahulprasad2318]

@@JJKK-nj1vb still it's more readable and maintainable.

[@rppt]

@@JJKK-nj1vb On the ARM Cortex M4, the assembly instruction VSQRT takes exactly 14 cycles for any 32 bit floating point. SQRT() being O(log-n) is only if you're assuming potentially arbitrarily large integers or arbitrarily precise floating points.

[@vadimkokielov2173]

I can't believe they marked the "math" solution O(1)?! Has rigor gone completely out of algorithm analysis?!!! The algorithm for computing square roots is Newton's Method -- which amounts to the same bisection in the case of square roots!! And it has the same logarithmic runtime??

[@NeetCode]

Yeah, I was wondering the same thing. It seems any "math" solution is marked O(1) but it's technically not the case.

[@prabhatracherla3098]

How was this easy question then? I mean code is easy, but the thought process was not

[@darkmatter2958]

i saw there was an o(1) solution it was return (sqrt(8*n+1)-1)/2

[@darkmatter2958]

can you explain it how it was derived

[@masternobody1896]

nice

[@pradiptasarma4867]

Arithmatic Progression.

[@flatmapper]

hard

[@HarvinderSandhuEsq]

Math formula is easier

[@Ericnguyencsca]

just return right instead

[@aabhishek4911]

Who has gone through school without learning gauss formula ? It is one of the very basic ones