Arranging Coins

Problem Statement

LeetCode-441: You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the $i^{th}$ 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.

Approach

The problem can be solved using binary search. The idea is to find the maximum number of rows that can be built with n coins. The number of coins required to build k rows is given by the formula:

$$ coins = \frac{k \times (k+1)}{2} $$

Using the above formula, we can find the maximum number of rows that can be built with n coins. The binary search algorithm can be used to find the maximum number of rows that can be built with n coins.

Implementation

Here is a Java implementation of the approach (using long to avoid overflow):

public int arrangeCoins(int n) {
    long start = 1;
    long end = n;
    
    while(start <= end){
        long mid = start + (end - start)/2;
        long total = mid*(mid+1)/2;
    
        if(total < n){
            start = mid+1;
        }else if(total > n){
            end = mid - 1;
        }else{
            return (int)mid;
        }
    }
    
    return (int)end;
}

Complexity Analysis

The time complexity for the above approach is $O(\log n)$.