Maximum Complete Staircase Rows

easy

You have $n$ identical coins that you want to arrange in a staircase structure. The $1^{\text{st}}$ row contains $1$ coin, the $2^{\text{nd}}$ row contains $2$ coins, the $3^{\text{rd}}$ row contains $3$ coins, and so on, such that the $k^{\text{th}}$ row contains $k$ coins.

Given the integer $n$, return the maximum number of complete rows that can be built using these coins.

Use binary search on the answer range $[0, n]$ to find the maximum integer $k$ such that the required number of coins $\frac{k(k + 1)}{2} \le n$.

Example 1

Input

[
  "5"
]

Output

Explanation. Row 1 takes 1 coin (4 left). Row 2 takes 2 coins (2 left). Row 3 requires 3 coins, but only 2 remain, so row 3 is incomplete. Total complete rows = 2.

Example 2

Input

[
  "8"
]

Output

Explanation. Row 1 takes 1 coin, Row 2 takes 2 coins, Row 3 takes 3 coins (total 6 coins used). Row 4 requires 4 coins, but only 2 remain. Total complete rows = 3.

Example 3

Input

[
  "0"
]

Output

Explanation. With 0 coins, no rows can be completed.

Example 4

Input

[
  "1"
]

Output

Explanation. 1 coin forms exactly 1 complete row.

Example 5

Input

[
  "3"
]

Output

Explanation. Row 1 takes 1 coin and Row 2 takes 2 coins (total 3 coins used). Exactly 2 complete rows are formed.

Example 6

Input

[
  "1000000000"
]

Output

44720

Explanation. Using binary search, 44720 * 44721 / 2 = 999963240 coins <= 10^9, while 44721 rows would require 1000007831 coins.

Follow-up: Can you solve this in $O(1)$ time complexity using a direct mathematical formula?

Constraints:

$0 \le n \le 2^{31} - 1$

Views: 2