All problems

Arranging Coins

Easy · binary search

You have n coins and want to lay them out as a staircase. The first row takes 1 coin, the second row takes 2 coins, the third row takes 3 coins, and so on: row k takes exactly k coins.

You build the rows in order and only count a row if you can fill it completely. The last row may be left unfinished when you run out of coins.

Return the number of complete rows in the staircase.

Examples

Example 1

Input: n = 5

Output: 2

Rows 1 and 2 use 1 + 2 = 3 coins. Row 3 needs 3 coins but only 2 are left, so it is unfinished.

Example 2

Input: n = 8

Output: 3

Rows 1 to 3 use 6 coins. Row 4 needs 4 but only 2 are left.

Example 3

Input: n = 1

Output: 1

Constraints