[LeetCode] 441. Arranging Coins

 Problem : https://leetcode.com/problems/arranging-coins/

Because 1 + 2 + 3 + ... + n = n * (n+1) / 2,  we can use binary search to find the answer.

class Solution:
    def arrangeCoins(self, n: int) -> int:
        
        # the possible result range = [left, right)
        left, right = 1, n + 1
        
        while left < right:
            mid = left + (right - left) // 2
            
            # total coions = mid * (mid + 1) / 2
            if mid *(mid+1)//2 <= n:
                left = mid + 1
            else:
                right = mid 
        
        return left - 1