Arranging Coins [Binary Search]

441.Arranging Coins

Math

Binary Search

Problem Statement:

You have n coins that you want to form into a staircase shape, where every k-th row must have exactly k coins. Given n, return the number of complete rows of the staircase you will build. Each row must be filled completely, using exactly k coins for the k-th row.

Example:

Input:

n = 5

→

Output:

2

You can form 2 complete rows: 1st row with 1 coin, 2nd row with 2 coins, and 3rd row is incomplete with 2 coins (needs 3).

Algorithm:

1. Use binary search to find maximum k where k*(k+1)/2 ≤ n
2. Handle potential overflow using long
3. Track maximum valid k as result
4. Return last valid k found

Complexity:

Time: O(log n) | Space: O(1)

Java Solution:

public int arrangeCoins(int n) {
    long low = 0, high = n;
    long k, coins, res = -1;
    
    while (low <= high) {
        k = low + (high - low)/2;
        coins = k * (k + 1)/2;
        
        if (coins <= n) {
            res = k;
            low = k + 1;
        } else 
            high = k - 1;
    }
    
    return (int) res;  
}

Python Solution:

def arrangeCoins(self, n: int) -> int:
    low, high = 0, n
    res = -1
    
    while low <= high:
        k = low + (high - low) // 2
        coins = k * (k + 1) // 2
        
        if coins <= n:
            res = k
            low = k + 1
        else:
            high = k - 1
            
    return res

C++ Solution:

int arrangeCoins(int n) {
    long low = 0, high = n;
    long k, coins, res = -1;
    
    while (low <= high) {
        k = low + (high - low)/2;
        coins = k * (k + 1)/2;
        
        if (coins <= n) {
            res = k;
            low = k + 1;
        } else 
            high = k - 1;
    }
    
    return res;
}