Community Problem
Arranging Coins
Difficulty: Easy
Find the largest k such that 1+2+...+k <= n, framed as a binary-search-on-answer warmup with a closed-form sanity check.
Arranging Coins
Find the largest k such that 1+2+...+k <= n, framed as a binary-search-on-answer warmup with a closed-form sanity check.
By @elenamuller
March 12, 2026
·
Updated May 18, 2026
484 views
15
4.4 (9)
I use this as the cleanest warmup for the binary-search-on-answer pattern. The closed-form k = floor((-1 + sqrt(1 + 8n)) / 2) exists, but the interview signal is the search version: define a monotone predicate, pin a closed interval that contains the answer, and walk through the off-by-one with the lo / hi update rules.
Arranging Coins
You have n coins and want to arrange them in a staircase shape where the i-th row contains exactly i coins. The last row may be incomplete (i.e. fewer than its full count). Return the largest number of complete rows you can build.
Formally, return the largest integer k such that 1 + 2 + 3 + ... + k <= n.
Examples
Example 1:
- Input:
n = 5 - Output:
2 - Explanation: Row 1 has 1 coin, row 2 has 2 coins (3 used). The third row would need 3 more coins, but only 2 are left, so it is incomplete.
Example 2:
- Input:
n = 8 - Output:
3 - Explanation: Rows of size 1, 2, 3 use exactly 6 coins. Row 4 would need 4 more, but only 2 are left.
Example 3:
- Input:
n = 1 - Output:
1 - Explanation: Exactly one full row.
Example 4:
- Input:
n = 0 - Output:
0 - Explanation: No coins, no rows.
Constraints
0 <= n <= 2^31 - 1
Follow-up
The closed-form answer is k = floor((-1 + sqrt(1 + 8n)) / 2). Why does the binary-search version still get asked? Because for very large n, sqrt on doubles can be off by 1 due to floating-point rounding, and binary search on integers is exact. Solve both ways and use one to validate the other.
Solution
Hints
Approach
This is the textbook "binary search on answer" warmup. The predicate p(k) := k*(k+1)/2 <= n is monotone in k (true for all k up to some boundary, false after), so we can binary-search for the largest feasible k.
Key insight
We are not searching INSIDE an array; we are searching the answer space [0, n]. The lower bound is trivially feasible (0 rows always fit). The upper bound n is generous (we will never use more rows than coins). Within that interval, we shrink toward the boundary between feasible and infeasible.
Algorithm
- Set
lo = 0,hi = n,ans = 0. - While
lo <= hi:mid = lo + (hi - lo) // 2(overflow-safe).- Compute
used = mid * (mid + 1) // 2. - If
used <= n:midrows fit, recordans = midand try larger:lo = mid + 1. - Else: too many,
hi = mid - 1.
- Return
ans.
Complexity
Metric Value
------ ---------
Time O(log n)
Space O(1)The answer space is [0, n], so we converge in ~log_2(n) iterations.
Why it works
f(k) = k*(k+1)/2 is strictly increasing in k for k >= 0. So the predicate f(k) <= n is true for k = 0..K* and false for k > K*, where K* is the answer. Binary search on a monotone predicate over a closed interval converges to the boundary, and the ans = mid recorded on every feasible mid ends up holding K*.
Pitfalls
- Overflow:
mid * (mid + 1)can blow past 32-bit range whennis near2^31 - 1, sincemidcan be up to ~65535. JS numbers are 64-bit floats so this fits, but languages with strict 32-bit ints need 64-bit promotion. - Closed vs half-open template: this writeup uses the closed interval
[lo, hi]with<=because the natural answer is the LARGEST feasible value, which the closed template tracks via theansvariable. The half-open[lo, hi)template also works but you have to derive the answer fromlo - 1. n = 0edge case: the loop runs withlo = hi = 0,mid = 0,used = 0 <= 0, returns 0. Confirm this trace manually.
Solution Code