Code Logo

Arranging Coins

Published at24 Jul 2026
Created by
Easy 1 views
Like0

You have n coins and want to build a staircase. The staircase consists of k rows where the i-th row has exactly i coins. The last row may be incomplete. Given n, find the maximum number of complete rows you can form. For example, with 5 coins you can make 2 complete rows (row 1 has 1 coin, row 2 has 2 coins) with 2 coins left over for an incomplete third row.

The total number of coins used for k complete rows is 1 + 2 + ... + k = k * (k + 1) / 2. We need the largest k such that k * (k + 1) / 2<= n. This is equivalent to solving the quadratic equation k² + k - 2n = 0 and taking the floor of the positive root.

A binary search approach iteratively narrows the range of possible k values between 0 and n. At each step, compute the total coins for mid rows using the formula. If the total equals n, return mid. If it's less than n, try more rows (lo = mid + 1). If it exceeds n, try fewer rows (hi = mid - 1). The answer is hi when the loop exits.

Edge cases include n = 0 (return 0), n = 1 (return 1), and large n where the multiplication must avoid overflow.

The arithmetic series formula k(k+1)/2 gives the total coins in k complete rows. Binary search efficiently finds the largest k satisfying this constraint without iterating row by row. The formula can also be derived from the sum of the first k natural numbers, a result discovered by the mathematician Gauss as a schoolchild.

Example Input & Output

Example 1
Input
8
Output
3
Explanation

1+2+3=6 <=8, 1+2+3+4=10>8. 3 complete rows.

Example 2
Input
0
Output
0
Explanation

No coins, no rows.

Example 3
Input
10
Output
4
Explanation

1+2+3+4=10 exactly. 4 complete rows.

Example 4
Input
1
Output
1
Explanation

Single coin fills row 1.

Example 5
Input
5
Output
2
Explanation

Rows 1+2=3, third row incomplete. 2 complete rows.

Algorithm Flow

Recommendation Algorithm Flow for Arranging Coins

Solution Approach

Find the maximum number of complete rows of coins that can be formed given n coins, where row k needs exactly k coins. The total coins needed for k rows is the arithmetic series sum k*(k+1)/2. Use binary search on the range [0, n] to find the largest k where k*(k+1)/2 <= n.

function arrangeCoins(n) {
  var left = 0, right = n;
  while (left <= right) {
    var mid = Math.floor((left + right) / 2);
    var total = mid * (mid + 1) / 2;
    if (total === n) return mid;
    if (total < n) left = mid + 1;
    else right = mid - 1;
  }
  return right;
}

The formula k*(k+1)/2 computes the total coins used by k rows. Binary search narrows down the exact k. When the loop ends, right holds the largest k that uses at most n coins.

Time complexity is O(log n), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int n) {
        int lo = 0, hi = n;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            long total = (long) mid * (mid + 1) / 2;
            if (total == n) return mid;
            if (total < n) lo = mid + 1;
            else hi = mid - 1;
        }
        return hi;
    }
}