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
Hint 1
k complete rows use k(k+1)/2 coins.
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
- Search
kover[0, n], tracking the best feasible value found. - For each
mid, compute the triangular numbermid * (mid + 1) / 2in a 64-bit type. - If it is at most
n,midrows fit — record it and search higher. - Otherwise search lower.
- 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 formidin 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 loJava
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