Leetcode :: Arranging Coins

Problem

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.

Guess

• 그냥 선형 탐색하면 쉬운 문제지만,
• 이분탐색으로도 해결이 가능해보인다.
• 등차수열 합공식 k*(k+1)/2 으로 이분탐색을 통해 n에 가장 가까운 k를 찾아내면 된다.

Solution

def arrangeCoins(n):
    left, right = 0, n

    while left <= right:
        mid = (left + right) // 2
        curr = mid*(mid+1) // 2

        if curr == n:
            return mid
        if curr > n:
            right = mid-1
        else:
            left = mid+1
        
    return right