777. The Tallest Complete Staircase

You have n coins and you are laying them out as a staircase. Row 1 takes 1 coin, row 2 takes 2 coins, row i takes i coins. A row counts only if it is COMPLETE.

Print how many complete rows you can build.

45 -> 9 1+2+...+9 = 45 exactly, nothing left over 8 -> 3 1+2+3 = 6, the 4th row wants 4 and only 2 remain 5 -> 2 1+2 = 3, two coins left, not enough for row 3 0 -> 0 not even the first row

## The counter

The first r rows consume 1 + 2 + ... + r, which is r (r + 1) / 2. So "how many coins does a staircase of height r need" is a closed form, and the question becomes: what is the largest r whose need is still within budget?

## Why the need is monotone

r (r + 1) / 2 strictly increases with r, because going from r to r + 1 adds r + 1 coins and r + 1 is positive. So once a height is unaffordable, every taller one is too. That is exactly the yes-then-no shape a binary search needs, and it is why a search over heights is legitimate while a search over, say, "coins left over" would not be.

## Adding rows one at a time is fine, until it is not

With n up to 10^15 the answer reaches about 4.5 * 10^7. A loop that adds one row at a time runs that many iterations, which is survivable in C and not in Python, and it is entirely avoidable.

## The bounds

The answer is at least 0 and at most 45000000, because 45000000 * 45000001 / 2 is already above 10^15. Any bound comfortably past the true answer works; a bound that is too LOW silently returns the bound itself, which looks like a plausible answer and is the reason this one is worth stating explicitly.

## The shape of this particular search

This is the maximise-a-feasible-value direction, so the midpoint rounds UP:

lo = 0, hi = 45000000 while lo < hi: mid = lo + (hi - lo + 1) / 2 if mid * (mid + 1) / 2 <= n: lo = mid else: hi = mid - 1

Rounding DOWN here is an infinite loop whenever hi == lo + 1 and the larger one is feasible: mid comes back as lo, the test passes, lo is set to lo, and nothing moves. That single character is the most common way this problem hangs.

## Relationship with problem 248

248 asks for the largest r with r * r <= n; this asks for the largest r with r (r + 1) / 2 <= n. Same direction, same rounding of the midpoint, same range of candidates with no array underneath it. Only the closed form inside the predicate changes, which is the cleanest demonstration that the skeleton is the part that transfers.

248's warning transfers as well. There is a closed form for this answer too, (sqrt(8n + 1) - 1) / 2, and it arrives as a floating point value that can land one off at a boundary, so it needs a correction step afterwards; the integer search multiplies and compares and needs none.

## Overflow

r (r + 1) at r = 4.5 * 10^7 is about 2 * 10^15. A 32-bit multiply wraps, the comparison becomes nonsense, and the search walks off to a random height. Multiply in 64 bits.

## Cost

Time O(log n). Space O(1).

Constraints - `0 ≤ n ≤ 10^15`