Arranging Coins

Easy
65.

Arranging Coins

Arranging Coins is an easy coding problem on math and binary search.

You have n coins and build a staircase where the i-th row has exactly i coins. Return the number of complete rows you can build.

Example 1

Input
n = 5
Output
2
Explanation
Rows 1 + 2 = 3 coins; the third row is incomplete.

Example 2

Input
n = 8
Output
3
Explanation
1 + 2 + 3 = 6; the fourth row is incomplete.

Constraints

  • 1 <= n <= 100000000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var arrangeCoins = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Arranging Coins — Solution in Python, Java & C++

Arranging Coins solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on math and binary search.

Arranging Coins is an easy coding problem on math and binary search.

  • Difficulty: Easy
  • Topics: Math, Binary Search
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You have n coins and build a staircase where the i-th row has exactly i coins. Return the number of complete rows you can build.

Example 1

Input: n = 5
Output: 2
Explanation: Rows 1 + 2 = 3 coins; the third row is incomplete.

Example 2

Input: n = 8
Output: 3
Explanation: 1 + 2 + 3 = 6; the fourth row is incomplete.

Constraints

  • 1 <= n <= 100000000

Hints for Arranging Coins

  1. Hint 1

    k complete rows use k(k+1)/2 coins.

  2. Hint 2

    Binary search (or solve the quadratic) for the largest k with k(k+1)/2 <= n.

How to solve Arranging Coins

k complete rows consume 1 + 2 + … + k = k(k + 1) / 2 coins, and that total only grows with k. So the question is the largest k whose triangular number does not exceed n — a monotone predicate, and binary search finds the boundary in logarithmic time even for n in the hundreds of millions.

Approach

  1. Search k over [0, n], tracking the best feasible value found.
  2. For each mid, compute the triangular number mid * (mid + 1) / 2 in a 64-bit type.
  3. If it is at most n, mid rows fit — record it and search higher.
  4. Otherwise search lower.
  5. Return the largest feasible k.

Why it works

Row i costs i coins, so the cost of k rows is the k-th triangular number — strictly increasing in k. That makes "fits within n" true up to some threshold and false beyond it, the single crossover binary search is built for. The closed form also solves directly via the quadratic k = floor((sqrt(8n + 1) - 1) / 2), though floating point can round the wrong way at exact boundaries, which is why the integer search is the safer choice.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • mid * (mid + 1) overflows 32 bits for mid in the tens of thousands upward — compute it as 64-bit, or the comparison silently goes negative.
  • Divide by two after multiplying (the product of consecutive integers is always even), not before.
  • The answer counts only complete rows, so a partial final row does not count.
  • Keep the last feasible mid; where the loop stops is not itself the answer.

Reference solution

Python

def arrangeCoins(n: int) -> int:
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid * (mid + 1) // 2 <= n:
            lo = mid
        else:
            hi = mid - 1
    return lo

Java

public static int arrangeCoins(int n) {
    long lo = 0, hi = n, best = 0;
    while (lo <= hi) {
        long mid = lo + (hi - lo) / 2;
        long used = mid * (mid + 1) / 2;
        if (used <= n) {
            best = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return (int) best;
}

C++

int arrangeCoins(int n) {
    long long lo = 0, hi = n, best = 0;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        long long used = mid * (mid + 1) / 2;
        if (used <= (long long) n) {
            best = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return (int) best;
}

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search