You have n coins and build a staircase where row k has exactly k coins. Return how many complete rows you can build.
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.
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
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.