357. Arranging Coins
You have n identical coins and want to stack them into a staircase: row 1 holds exactly 1 coin, row 2 holds exactly 2, and in general row i holds exactly i coins.
You fill rows from the top down until you run out. The last row may be left unfinished — an unfinished row does not count.
For the given n, report how many rows end up completely filled.
Example 1:
Input: n = 5
Output: 2
Explanation: Rows 1 and 2 use 1 + 2 = 3 coins. The remaining 2 coins cannot finish row 3 (which needs 3), so only 2 rows are complete.
Example 2:
Input: n = 8
Output: 3
Explanation: Rows 1, 2 and 3 use 1 + 2 + 3 = 6 coins; the 2 left over cannot finish row 4.
Constraints:
- 1 ≤ n ≤ 2³¹ - 1
- Intermediate products like k * (k + 1) can exceed 32-bit range — compute them in 64 bits.
Hints:
The first k complete rows use exactly 1 + 2 + … + k = k(k+1)/2 coins. So you are looking for the largest k with k(k+1)/2 <= n.
k(k+1)/2 grows monotonically with k, and "largest k satisfying a monotone condition" is a textbook binary search — or solve k(k+1)/2 = n directly with the quadratic formula and floor the root (carefully, with integer arithmetic).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 5
Expected output: 2