The problem
You build a staircase where row i holds i coins. Given n coins, how many COMPLETE rows can you build?
Stuck? Reveal hints one at a time
How to approach it
- 1Binary search k in [1, n].
- 2coins(mid) = mid × (mid + 1) / 2. If ≤ n, record mid and go higher; else lower.
- 3Return the recorded k.
Key insight
Any counting function that grows monotonically (here, triangular numbers) turns "how many fit?" into a boundary search.
The solution
Watch out for
- mid*(mid+1)/2 can overflow 32-bit ints near n = 2³¹ — use 64-bit math or the divide-first form.
- The closed-form ⌊(√(8n+1)−1)/2⌋ works but float precision at the boundary needs a verify step.