You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
 
Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.



Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

Difficulty: introductory

Starter code:

class Solution:
    def arrangeCoins(self, n: int) -> int:
        

Solutions:
class Solution:
     def arrangeCoins(self, n):
         """
         :type n: int
         :rtype: int
         """
         #brute force:
         #m = i (i+1) / 2 
         #i = 0
         #while True:
         #    row = i * (i+1) / 2
         #    if n - row < 0:
         #        return i - 1
         #    i += 1
             
         # 2m = i (i+1)  
         # i**2 + i - 2m = 0
         # i = -1 + sqr(8m) / 2
         return int((math.sqrt(8*n + 1)-1)/2 ) 
         


class Solution:
     def arrangeCoins(self, n):
         """
         :type n: int
         :rtype: int
         """
         return int((math.sqrt(8*n+1)-1)/2)

class Solution:
     def arrangeCoins(self, n):
         """
         :type n: int
         :rtype: int
         """
         return int(((8*n+1)**0.5-1)/2)

class Solution:
     def arrangeCoins(self, n):
         """
         :type n: int
         :rtype: int
         """
         
         return int((2 * n + 0.25) ** 0.5 - 0.5)

class Solution:
     def arrangeCoins(self, n):
         """
         :type n: int
         :rtype: int
         """
         # result = 0
         # if n < 2 :
         #     return n
         # for i in range(1,n+1):
         #     result += i
         #     if result > n:
         #         return i-1
         
         return  int(((2*n)+1.0/4)**0.5 - 0.5)
         
         
         
         
 #         left, right = 0, n
 #         while left <= right:
 #             mid = (left + right) // 2
 #             if self.totalCoins(mid) <= n < self.totalCoins(mid + 1) :
 #                 return mid
 #             elif n < self.totalCoins(mid):
 #                 right = mid
 #             else:
 #                 left = mid + 1
     
     
 #     def totalCoins(self, row):
 #         return (1 + row)*row //2


class Solution:
     def arrangeCoins(self, n):
         """
         :type n: int
         :rtype: int
         """
         return int(((8*n + 1)**0.5 - 1)/2)

class Solution:
     def arrangeCoins(self, n):
         """
         :type n: int
         :rtype: int
         """
         if n == 0:
             return 0
         upper = math.ceil(math.sqrt(2 * n))
         lower = math.floor(math.sqrt(2 * n)) - 2
         for k in range(lower+1, upper):
             if (k+1)*k <= 2*n and (k+2)*(k+1) > 2*n:
                 return k


class Solution(object):
     def arrangeCoins(self, n):
         """
         :type n: int
         :rtype: int
         """
         return int(math.sqrt(2 * n + 0.25) - 0.5)

class Solution:
     def arrangeCoins(self, n):
         """
         :type n: int
         :rtype: int
         """
         return int((1+8*n)**0.5 - 1) // 2