441 Arranging Coins

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

 

constraints :

• 1 <= n <= \(2^{31}\) - 1

2. Algorithms

To calculate sum of range 1 - n, we can apply formular next : \(n * (n + 1) / 2\). So we can find complete rows using binary search algorithm.

 

To store last integer that cumulative sum of range 1- n is smaller than n, we will store middle point before update start.

 

1. Start
2. Declare two variables start, end. Initialize them with 0, n.
3. Repeat the steps until start is bigger than end.
   1. Calculate middle point between start and end.
   2. Calculate range sum between 1 - n. Store the result in variable cumsum.
   3. If cumsum is smaller than n, store middle into variable res and update start as middle + 1.
   4. If cumsum is bigger than n, update end as middle - 1.
4. Return the result after the loop ends.
5. End

3. Codes

class Solution:
    def arrangeCoins(self, n: int) -> int:
        start, end = 0, n
        res = 0
        
        while start <= end : 
            mid = (start + end) // 2
            cumsum = (mid * (mid + 1)) / 2
            
            if cumsum <= n : 
                res = mid
                start = mid + 1
            else : 
                end = mid - 1
                
        return res

4. Conclusion