441. Arranging Coins

Description:

You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.

Given the integer n, return the number of complete rows of the staircase you will build.

 

'''
[1] brute force)

idea::
fill stairs with coins from top.

code::
def arrangeCoins(self, n: int) -> int:
    cur_row=1
    while n>=cur_row:
        n-=cur_row
        cur_row+=1

    return cur_row-1
    
-T/C: O(r) # r==complete rows
-S/C: O(1)
'''

'''
[2] math)

idea::
let, r==row
then, r*(r+1)/2 <= n <=> r <= ((8*n+1)**0.5 -1)/2

code::
def arrangeCoins(self, n: int) -> int:
    return int(((8*n+1)**0.5 -1)//2)
    
-T/C: O(1)
-S/C: O(1)
'''

'''
[3] binary search)

idea::
left,right=1,n
compare mid*(mid+1)//2 with n. and then, move left or right

code::
def arrangeCoins(self, n: int) -> int:
    left,right=1,n

    while left<=right:
        mid=(left+right)//2
        mid_coins=(mid*(mid+1))//2

        if mid_coins==n:
            return mid
        elif mid_coins>n:
            right=mid-1
        else:
            left=mid+1
    return right

-T/C: O(logn)
-S/C: O(1)
'''
class Solution:
    def arrangeCoins(self, n: int) -> int:
        left,right=1,n
        
        while left<=right:
            mid=(left+right)//2
            mid_coins=(mid*(mid+1))//2
            
            if mid_coins==n:
                return mid
            elif mid_coins>n:
                right=mid-1
            else:
                left=mid+1
        return right