Arranging Coins
Count how many complete rows of a coin staircase n coins can fill. A row-by-row loop in O(√n), then binary search on the number of rows in O(log n).
Updated Medium read: 7 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Build row by row | O(√n) | O(1) |
| Binary search on the row count | O(log n) | O(1) |
The problem
You have n coins and lay them out as a staircase: one coin in the first row, two in the second, three in the third, and so on. Each row must be filled before the next one is started. The last row you start may be left unfinished.
Return the number of rows that are completely filled.
n = 8
row 1: ●
row 2: ● ●
row 3: ● ● ●
row 4: ● ● (needs 4 coins, only 2 are left)
→ 3 complete rowsn = 6 → 3 (1 + 2 + 3 uses all six)
n = 1 → 1
n = 2 → 1 (the second row gets one coin of two)Restating the question
A staircase of k complete rows uses 1 + 2 + ... + k coins. That total has a well-known short form:
coins for k rows = k × (k + 1) / 2For 3 rows it gives 3 × 4 / 2 = 6, and for 4 rows it gives 4 × 5 / 2 = 10. So the question becomes: what is the largest k for which k × (k + 1) / 2 is at most n?
Approach 1: build row by row
Do what the description says. Keep handing out coins, one row at a time, for as long as the next row can be paid for.
JavaScript
function arrangeCoinsLinear(n) {
let rows = 0;
let remaining = n;
// The next row needs rows + 1 coins.
while (remaining >= rows + 1) {
rows++;
remaining -= rows;
}
return rows;
}Python
def arrange_coins_linear(n):
rows = 0
remaining = n
# The next row needs rows + 1 coins.
while remaining >= rows + 1:
rows += 1
remaining -= rows
return rowsThe loop runs once for each complete row. Since k rows use roughly k² / 2 coins, the number of rows is roughly the square root of 2n.
Time O(√n). Space O(1).
For n up to about two thousand million, that is at most some 65,000 steps, which is perfectly usable. Binary search brings it down to about 31.
Approach 2: binary search on the row count
Rather than building the staircase, guess the number of rows and check the guess with the formula. The check is a yes-or-no question: "do k complete rows fit in n coins?"
The answers to that question are in a helpful order. If 4 rows fit, 3 rows certainly do. If 4 rows do not fit, 5 rows cannot either. So the answers are "yes" up to some point and "no" after it:
n = 8
rows k: 0 1 2 3 4 5 6 7 8
coins needed: 0 1 3 6 10 15 21 28 36
fits in 8? yes yes yes yes no no no no no
↑
the largest k that fitsA list of answers that switches once is exactly what binary search needs. This is the "largest value that passes" form of the binary search on the answer pattern.
- Range. At least 0 rows, at most
nrows (a row holds at least one coin). - Test.
k × (k + 1) / 2 <= n. - Direction. Passes come first, so keep the middle when it passes and move
loup to it.
JavaScript
function arrangeCoins(n) {
let lo = 0;
let hi = n;
while (lo < hi) {
// Round the middle UP, so that lo = mid always makes progress.
const mid = lo + Math.ceil((hi - lo) / 2);
if ((mid * (mid + 1)) / 2 <= n) {
lo = mid; // mid rows fit: the answer is mid or more
} else {
hi = mid - 1; // mid rows do not fit: the answer is less
}
}
return lo;
}Python
def arrange_coins(n):
lo = 0
hi = n
while lo < hi:
# Round the middle UP, so that lo = mid always makes progress.
mid = lo + (hi - lo + 1) // 2
if mid * (mid + 1) // 2 <= n:
lo = mid # mid rows fit: the answer is mid or more
else:
hi = mid - 1 # mid rows do not fit: the answer is less
return loThe loop keeps one promise the whole time: lo rows always fit, and nothing above hi does. It starts true (0 rows need 0 coins) and each branch keeps it true. When lo and hi meet, that single value is the largest count that fits.
Why the middle is rounded up
Take a range of two values, lo = 3 and hi = 4. Rounded down, the middle is 3. If 3 passes, the code sets lo = 3, which is where it already was, and the loop repeats for ever. Rounded up, the middle is 4: either lo becomes 4 or hi becomes 3, and the loop ends. In Python, (hi - lo + 1) // 2 is the rounded-up half of the gap.
Walkthrough
n = 8:
| lo | hi | mid | Coins for mid rows | Fits in 8? | Action |
|---|---|---|---|---|---|
| 0 | 8 | 4 | 10 | No | hi = 3 |
| 0 | 3 | 2 | 3 | Yes | lo = 2 |
| 2 | 3 | 3 | 6 | Yes | lo = 3 |
| 3 | 3 | lo equals hi: return 3 |
Three tests. Six coins make three rows, and the two left over are not enough for a fourth.
Time O(log n). Space O(1).
Comparing the approaches
| Approach | Time | Space | Steps for n = 1,000,000,000 |
|---|---|---|---|
| Build row by row | O(√n) | O(1) | 44,720 |
| Binary search on the row count | O(log n) | O(1) | About 30 |
Both are fast enough for this problem's limits. The reason to learn the second is that the same three decisions (range, test, direction) solve much harder questions, such as Koko Eating Bananas, where there is no neat formula and the test has to loop over an array.
A formula also exists
Solving k × (k + 1) / 2 = n for k with the quadratic formula gives k = (√(8n + 1) - 1) / 2, rounded down. That is a single calculation. Its weakness is that square roots are worked out with floating-point numbers, which are only approximate: for very large n the result can land a hair below a whole number and round down to the wrong row count. The binary search uses whole-number arithmetic only, so it has no such risk.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(arrangeCoins(8)); // 3
console.log(arrangeCoins(6)); // 3
console.log(arrangeCoins(2)); // 1
console.log(arrangeCoins(1000000000)); // 44720Python
print(arrange_coins(8)) # 3
print(arrange_coins(6)) # 3
print(arrange_coins(2)) # 1
print(arrange_coins(1000000000)) # 44720The comment after each line is the result you should see.
Common mistakes
- Rounding the middle down. With
lo = midin the passing branch, a rounded-down middle gives an endless loop as soon as two candidates are left. - Testing with
<instead of<=. When the coins fill the last row exactly, as withn = 6, that row counts. A strict comparison returns one row too few. - Counting the unfinished row. The question asks for complete rows only: 8 coins give 3, not 4.
- Overflow in other languages.
mid * (mid + 1)can be far larger thann. In Java or C++ it needs a 64-bit type (long), or the product wraps round to a wrong, possibly negative, number. JavaScript numbers and Python integers handle the sizes in this problem without trouble. - Using true division in Python.
mid * (mid + 1) / 2gives a float.//keeps everything in whole numbers.
Original problem: LeetCode 441: Arranging Coins