Arranging Coins

Easy Math

You have n coins and want to stack them into a triangle: the first row holds 1
coin, the second holds 2, the third holds 3, and so on. A row only counts as
complete when every coin it needs is available, so the question becomes: what
is the largest k with 1 + 2 + ... + k <= n? That sum is the triangular number
k * (k + 1) / 2, which grows steadily as k grows. Binary search over candidate
k values finds the answer in O(log n) time even when n reaches 2^31 - 1.
- Input: an integer n, the total number of coins.
- Output: the number of complete full rows, a single integer.
- Constraints: 1 <= n <= 2^31 - 1.
- Edge cases: n = 1 (one row with a single coin); exact triangular numbers such as n = 6 (three rows); leftovers that cannot finish the next row (n = 8 still gives 3).

Input Format

Line 1: n, a single integer

Output Format

Print a single integer.

Constraints

1 <= n <= 2^31 - 1.

Hints

Hint 1: k complete rows consume exactly the triangular number k * (k + 1) / 2 coins.

Hint 2: Binary search k over 1..n and keep the largest k whose triangular number still fits inside n.

Hint 3: n can reach 2^31 - 1, so use 64-bit or double arithmetic for the product to avoid overflow.

Examples

Example 1:

Input

Output

Example 2:

Input

Output

Code runs on a free external sandbox (wandbox). Nothing executes on Scriptly's shared host.

Community solutions

Title

Language

Approach / explanation

Code

Fastest accepted solutions

Code wandbox sandbox

Ready

Compiling & running on the sandbox

Run your solution with the sample test cases to see results here.