Arranging Coins (LeetCode 441): Binary Search or the Quadratic Formula

You have n coins and build a staircase where row k has exactly k coins. Return how many complete rows you can build.

Binary search on rows

Building k rows takes k * (k + 1) / 2 coins, which grows monotonically, so binary search for the largest k that fits:

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

O(log n) time.

Closed form

Solve k^2 + k - 2n <= 0: k = floor((sqrt(8n + 1) - 1) / 2). In Python use math.isqrt to avoid floating-point error on large n:

import math
def arrange_coins(n: int) -> int:
    return (math.isqrt(8 * n + 1) - 1) // 2

Talking points

Mention the monotonic predicate that justifies binary search, the upper-mid choice that avoids an infinite loop, and why integer square root beats sqrt. For practice explaining binary-search invariants out loud, Linkjob AI can help (learn more).

Disclosure: I work on Linkjob AI.