Arranging Coins LeetCode Solution

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

            

Try Problem here