Quoestion: Click Here



Approach:

If we take a close look at problem we  need to find the greatest m,such that m(m+1)/2 <= n or m^2 + m - 2n <= 0. This is quadriatic inequality,to solve we should find roots of m^2 + m - 2n = 0.


m1,2=⟨-1±√1+8n⟩/2 or m >=  (2n +0.25)½ - 0.5

Complexity:
  • Time:O(1)
  • Space:O(1)
Pyhton Code:
Class Solution:
    def arrangeCoins(self,n):
        return int(sqrt(2*n + 0.25) - 0.5)

Second Approach:
 we add arrange i coins in kth row and decrease n by k  (n=n-i) until i >= n and finally we return i

Python Code:
    def arrangeCoins(self, n):
        if n==0:
            return n
        i =0
        while i<n:
            n-=(i+1)
            i+=1
        return i