visual walkthrough
Arranging Coins
Monotonic formula check, with an O(1) math alternative.
The idea
A staircase of k rows uses 1 + 2 + … + k = k(k+1)/2 coins, and that grows with k.
So "can I build k rows?" is yes for small k and no after some point: binary search for the last yes.
Complexity
| approach | time | space |
|---|---|---|
| Build row by row | O(√n) | O(1) |
| Binary search on rows | O(log n) | O(1) |