Code Logo

Arranging Coins

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Arranging Coins

Solution Approach

Binary search k between 0 and n. Use formula k*(k+1)/2 to check if mid rows use at most n coins.

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

Time O(log n), Space 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;
    }
}