Arranging Coins

You have n coins and want to build a staircase where row 1 has 1 coin, row 2 has 2 coins, and in general row i has i coins. The last row may be incomplete. Return the number of complete rows. This is LeetCode 441.

Example 1
Input: n = 5
Output: 2
Explanation: rows of 1 and 2 coins use 3 coins; the 2 coins left cannot fill row 3. Staircase built with 5 coins: two complete rows
Example 2
Input: n = 8
Output: 3
Explanation: rows of 1, 2 and 3 coins use 6 coins; the 2 left cannot fill row 4. Staircase built with 8 coins: three complete rows

How to Think About It

Step 1: Count the coins in k full rows

k complete rows use 1 + 2 + … + k coins. That sum has a closed form, k(k + 1) / 2: pairing the first and last rows, then the second and second-to-last, gives pairs that each add up to k + 1. For example, 4 rows use 4 × 5 / 2 = 10 coins.

Step 2: Turn it into a search

The answer is the largest k with k(k + 1) / 2 <= n. As k grows, the coins needed only grow, so the test "do k rows fit?" is true for small k and false from some point on. Binary search finds the last true.

Step 3: Search for the last true without skipping it

  • If mid rows fit, mid might be the answer: keep it with lo = mid.
  • Otherwise mid is too many: hi = mid - 1.

Because one branch sets lo = mid, the middle must be rounded up: mid = lo + (hi - lo + 1) / 2. With the usual rounding down, a range of two values like lo = 2, hi = 3 gives mid = 2, sets lo = 2 again, and loops forever.

Step 4: Use long

For n near 231, mid * (mid + 1) overflows an int, so the variables are long.

Walkthrough

n = 8:

lohimid (rounded up)Coins for mid rowsDecision
08410more than 8: hi = 3
0323fits: lo = 2
2336fits: lo = 3
33lo == hi: answer 3

Java Solution

This is the last-true template: the midpoint rounds up so that lo = mid always moves forward, and long keeps mid * (mid + 1) from overflowing.

Java
public class ArrangingCoins {

    // Largest k with 1 + 2 + ... + k = k(k + 1) / 2 <= n
    public static int arrangeCoins(int n) {
        long lo = 0;
        long hi = n;
        while (lo < hi) {
            long mid = lo + (hi - lo + 1) / 2;    // round up, so lo = mid always makes progress
            if (mid * (mid + 1) / 2 <= n) {
                lo = mid;                         // mid full rows fit
            } else {
                hi = mid - 1;
            }
        }
        return (int) lo;
    }

    public static void main(String[] args) {
        System.out.println(arrangeCoins(5));            // 2
        System.out.println(arrangeCoins(8));            // 3
        System.out.println(arrangeCoins(2147483647));   // 65535
    }
}

The original implementation, ArrangeCoins.java, is on GitHub. Solving k(k + 1) / 2 = n with the quadratic formula gives a direct answer, (int) ((Math.sqrt(8.0 * n + 1) - 1) / 2), but floating-point rounding needs care for large n, which binary search avoids.

Complexity

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