Arranging Coins
Easy · Binary Search · Math · Binary Search
Problem
You have n coins and want to build a staircase with them. Row 1 holds 1 coin, row 2 holds 2 coins, and in general row i holds exactly i coins. Rows are filled in order, so only the last row may be left incomplete.
Return the number of rows that are completely filled.
Examples
Input: n = 10 Output: 4
Rows of 1, 2, 3 and 4 coins use exactly 10 coins.
Input: n = 12 Output: 4
Four full rows use 10 coins; the 2 left cannot fill a row of 5.
Input: n = 2 Output: 1
Row 1 takes one coin, and row 2 gets only one of the two it needs.
Constraints
- 1 <= n <= 2^31 - 1
Approaches
- Baseline: fill rows one at a time — time O(√n), space O(1)
Follow-up
Solving k(k + 1) / 2 <= n directly gives k = floor((sqrt(8n + 1) - 1) / 2), an O(1) answer. Floating-point square roots can be off by one near perfect squares, so compute it with an exact integer square root (math.isqrt in Python), or nudge the result up or down after a float estimate.
Related problems
Start free on Cariara · Coding problems · System design studio
