Abstract / Summary

Find the highest floor such that arranging coins in a staircase shape uses at most all the coins available.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 48% (1+ million submissions).

Typical patterns to solve this problem:

• Binary Search
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “arrange coins” problem: given a total number of coins n, determine the maximum number of complete rows that can be formed when the first row contains one coin, the second row two coins, and so on. The algorithm iteratively builds rows until the cumulative count reaches or exceeds the target, then adjusts the result if an overshoot occurred. It uses 64-bit integers to safely handle large inputs and returns the final row count as a standard 32-bit integer.

Key Steps

The method begins by initializing two 64-bit counters:

int64_t step = 0;
int64_t available = 0;

step represents the current row index (the number of coins that would be placed in the next row), while available accumulates the total number of coins used so far.

The core of the algorithm is a while loop that continues as long as the accumulated coins are fewer than the input n:

while (available < n)
{
    step++;
    available += step;
}

Inside the loop, step is incremented to represent the next row, and that row’s coin count is added to available. This process repeats until available meets or exceeds n.

After the loop terminates, a conditional check determines whether the last addition overshot the target:

if (n < available)
    step--;

If the total coins used (available) exceed the supplied amount (n), the algorithm decrements step to discard the incomplete final row, ensuring the returned value reflects only fully formed rows.

Finally, the method returns the computed row count, implicitly converting the 64-bit step back to a 32-bit int:

return step;

Edge Cases Handled

The use of int64_t for both step and available guarantees correct behavior when n approaches the upper limits of a 32-bit signed integer. For very small inputs, such as n = 0 or n = 1, the loop condition available < n correctly prevents any iteration for n = 0, leaving step at zero, which is the appropriate result. For n = 1, the loop runs once, step becomes 1, available becomes 1, and the subsequent overshoot check does not trigger, yielding a correct result of one row.

When n is exactly the sum of the first k natural numbers, the loop stops with available == n. The overshoot condition n < available evaluates to false, so step remains at k, correctly reporting the full number of rows without unnecessary adjustment.

If n falls between two triangular numbers, the loop will exceed n on the iteration that would create the next row. The conditional decrement then removes that incomplete row, delivering the largest k such that the sum of the first k numbers does not surpass n.

Performance Optimizations

The algorithm operates with a single linear pass over the potential row count. By incrementally adding the next row size to a running total, it avoids recomputing triangular numbers from scratch on each iteration, which would be more costly. The use of simple arithmetic (step++ and available += step) ensures minimal overhead per loop cycle.

Choosing 64-bit integers eliminates the need for overflow checks within the loop, allowing the addition to proceed without branching or extra logic. This design choice keeps the hot loop tight and enables the compiler to generate efficient machine code.

The final conditional adjustment (if (n < available) step--;) is executed at most once, after the loop completes, adding negligible cost while guaranteeing correctness for the overshoot scenario. Overall, the implementation balances simplicity with sufficient safeguards to handle the full range of valid inputs efficiently.

Imagine building a little pyramid out of shiny blocks. You have a big pile of blocks and you want to see how many rows you can make. For the top row, you put down one block. For the second row, you put down two blocks. For the third row, you put down three blocks. You keep adding rows one by one until you run out of blocks.

The code starts by looking at your pile. It has two helpers. One helper counts which row you are currently building, and the other helper keeps track of the total number of blocks you have used so far. The code uses a loop to keep building rows as long as the total number of blocks used is still smaller than the number of blocks you started with. Inside that loop, it adds one row to the counter and then adds that number of blocks to the total pile being used.

Sometimes, you might try to build a full row but you realize you do not have quite enough blocks left to finish it. When that happens, the code notices that you used more blocks than you actually had. To fix this, it takes that last incomplete row away so that you only count the rows that were finished perfectly. After all that checking, the code knows exactly how many full rows you were able to stack up.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: sublinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java					Go
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	chandansgowda		Python
	charles-wangkai				Java
	everthis			JS
	fartem							Ruby
	fengvyi	C++
	fpdjsns	C++
	halfrost									Go
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune	C++
	linouk23	C++
	lkwq007		Python
	MacJim	C++
	qiyuangong		Python
	ruoru						Rust
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
	yuanliu666								Kotlin
	YuriSpiridonov		Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
linouk23	C++
lkwq007	Python
MacJim	C++
qiyuangong	Python
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++
yuanliu666	Kotlin
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality