Arranging Coins - Leetcode 441 - Python

0:00 - Read the problem
1:10 - Drawing Explanation
9:58 - Coding Explanation

leetcode 441

#facebook #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[weaponkid]

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!

[shrimpo]

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

[reisturm]

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

[sankhadip_roy]

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

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

[VishalTyagi-zn]

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)

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

[augustshen]

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

[pabloarkadiuszkalemba]

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

[mearaftadewos]

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

[yuhuipang]

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

[Chirayu]

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!

[ayoubalem]

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

[mearaftadewos]

Thank you dear NeetCode. My fav channel.

[sushantrocks]

Return the positive root of the quadratic eqn: k(k+1)/2 = n

return int(math.sqrt(1+8*n)-1)//2

[harshavardhanveerannanaval]

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<=r):
mid=(l+r)/2
if(getCoins(mid)<=n):
ans=mid
l=mid+1
else:
r=mid-1

return(ans)

[mohamedhesham]

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

[maamounhajnajeeb]

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 <= end:
mid = (start+end)//2
guess = mid*(mid+1)//2
if guess > n:
end = mid-1
elif guess <= n:
start = mid+1
row = mid
return row

[ilihaspatel]

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

[crazyloveever]

Do you use any extension to write on websites when connected with writing tablet?