Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

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

ApproachTimeSpace
Build row by rowO(√n)O(1)
Binary search on the row countO(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 rows
n = 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) / 2

For 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 rows

The 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 fits

A 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 n rows (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 lo up 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 lo

The 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)); // 44720

Python

print(arrange_coins(8))  # 3
print(arrange_coins(6))  # 3
print(arrange_coins(2))  # 1
print(arrange_coins(1000000000))  # 44720

The comment after each line is the result you should see.

Common mistakes

  • Rounding the middle down. With lo = mid in 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 with n = 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 than n. 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) / 2 gives a float. // keeps everything in whole numbers.

Original problem: LeetCode 441: Arranging Coins