444. Arranging Coins (Binary Search Approach)

You have n coins and want to arrange them in a staircase: row k contains exactly k coins. Return the total number of complete rows. Solve in O(log n) using binary search.

Input: A non-negative integer n.

Output: Number of complete staircase rows.

Examples

Input: 5
Output: 2
Explanation: Row 1:1, Row 2:2, Row 3 needs 3 but only 2 left. 2 complete rows.

Input: 8
Output: 3
Explanation: Rows: 1+2+3=6<=8, 1+2+3+4=10>8. 3 complete rows.

Input: 1
Output: 1
Explanation: Row 1 uses 1 coin. 1 complete row.

Constraints

• 0 <= n <= 2^31 - 1

Asked by