Arranging Coins

easy math binary search

Problem

You have n coins to arrange in a staircase where row i has exactly i coins. Return the number of complete rows.

Inputn = 8

Output3

Rows of size 1, 2, 3 use 6 coins; only 2 left, can't fill row 4.

def arrange_coins(n):
    lo, hi = 1, n
    while lo <= hi:
        mid = (lo + hi) // 2
        used = mid * (mid + 1) // 2
        if used <= n:
            lo = mid + 1
        else:
            hi = mid - 1
    return hi

function arrangeCoins(n) {
  let lo = 1, hi = n;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    const used = mid * (mid + 1) / 2;
    if (used <= n) lo = mid + 1;
    else hi = mid - 1;
  }
  return hi;
}

class Solution {
    public int arrangeCoins(int n) {
        long lo = 1, hi = n;
        while (lo <= hi) {
            long mid = (lo + hi) / 2;
            long used = mid * (mid + 1) / 2;
            if (used <= n) lo = mid + 1;
            else hi = mid - 1;
        }
        return (int) hi;
    }
}

int arrangeCoins(int n) {
    long long lo = 1, hi = n;
    while (lo <= hi) {
        long long mid = (lo + hi) / 2;
        long long used = mid * (mid + 1) / 2;
        if (used <= n) lo = mid + 1;
        else hi = mid - 1;
    }
    return (int) hi;
}

Explanation

We want the largest number of complete staircase rows we can build with n coins. Building k rows uses 1 + 2 + … + k = k(k+1)/2 coins, and that total only grows as k grows — which makes it perfect for binary search.

We search for k in the range [1, n]. For a midpoint mid, we compute used = mid * (mid + 1) / 2, the coins a full mid-row staircase needs.

If used <= n, then mid rows are affordable, so we might be able to do even more — we move right with lo = mid + 1. If used > n, mid is too greedy, so we shrink with hi = mid - 1.

When the loop ends, hi holds the largest row count that still fit, and that is the answer.

Example: n = 8. Rows 1, 2, 3 use 6 coins (≤ 8, fine), but 4 rows would need 10 (> 8, too many). The search settles on 3. The whole thing runs in O(log n).

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