Complete rows of a coin staircase
You build a staircase from n coins: the first row holds 1 coin, the second 2, the k-th row
k coins. The last row may be left incomplete. Return the number of complete rows.
Examples
| Input | Output | Why |
|---|---|---|
n = 5 | 2 | Rows of 1 and 2 use 3 coins; the third row has only 2 of its 3. |
n = 8 | 3 | 1 + 2 + 3 = 6; the fourth row would need 4 more. |
n = 1 | 1 |
Constraints
- 1 ≤ n ≤ 2³¹ − 1
Hints
Hint 1
k complete rows use 1 + 2 + … + k = k(k + 1)/2 coins.
Hint 2
That total grows with k, so "k(k + 1)/2 ≤ n" is true up to some k and false after it. Find the last true.
Hint 3
k can reach about 65,535 and k(k + 1) about 4.3 × 10⁹, beyond 32 bits. Use 64-bit arithmetic.
Where people lose marks
- Computing k(k + 1)/2 in 32 bits when k can be close to n.
- Rounding the midpoint down while setting lo = mid.
- Returning the number of rows started rather than completed.
Dry run on 40
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 8lo0hi40
Candidates 0 to 40. More rows always need more coins, so "the rows fit" holds up to some k and then fails. mid rounds up.
-
Step 2 / 8lo0mid20hi40
20 rows need 20·21/2 = 210 coins, more than 40. 20 fails, so does everything above it: hi = 19.
-
Step 3 / 8lo0mid10hi19
10 rows need 10·11/2 = 55 coins, more than 40. 10 fails, so does everything above it: hi = 9.
-
Step 4 / 8lo0mid5hi9
5 rows need 5·6/2 = 15 coins, within 40. 5 works, so the answer is 5 or larger: lo = 5.
-
Step 5 / 8lo5mid7hi9
7 rows need 7·8/2 = 28 coins, within 40. 7 works, so the answer is 7 or larger: lo = 7.
-
Step 6 / 8lo7mid8hi9
8 rows need 8·9/2 = 36 coins, within 40. 8 works, so the answer is 8 or larger: lo = 8.
-
Step 7 / 8lo8mid9hi9
9 rows need 9·10/2 = 45 coins, more than 40. 9 fails, so does everything above it: hi = 8.
-
Step 8 / 8answer8
lo = hi = 8: 8 rows use 36 coins, and 9 rows would need 45. The answer is 8.
How to think about it
Building k complete rows costs T(k) = k(k + 1)/2 coins, the k-th triangular number.
T is increasing, so the test T(k) ≤ n holds for every k up to the answer
and fails for every k after it. The answer is the last k that passes.
The candidates run from 0 to n (a wider range costs only a few extra steps). Search for the last
true: keep mid when it passes, discard it when it fails, and round the midpoint up so that
lo = mid always makes progress.
The closed form, k = ⌊(√(8n + 1) − 1)/2⌋, is quicker to type but relies on a
floating-point square root that can be off by one for large n. If you use it, correct the result with the same
integer test.
Complexity. Time O(log n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def arrange_coins(n):
lo, hi = 0, n # the answer is in [lo, hi]
while lo < hi:
mid = (lo + hi + 1) // 2 # round up
if mid * (mid + 1) // 2 <= n:
lo = mid # mid rows fit
else:
hi = mid - 1
return lolong long solve(long long n) {
long long lo = 0, hi = n; // the answer is in [lo, hi]
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2; // round up
if (mid * (mid + 1) / 2 <= n) lo = mid; // 64-bit
else hi = mid - 1;
}
return lo;
}class Solution {
public int arrangeCoins(int n) {
long lo = 0, hi = n; // the answer is in [lo, hi]
while (lo < hi) {
long mid = lo + (hi - lo + 1) / 2; // round up
if (mid * (mid + 1) / 2 <= n) lo = mid;
else hi = mid - 1;
}
return (int) lo;
}
}function arrangeCoins(n) {
let lo = 0, hi = n; // the answer is in [lo, hi]
while (lo < hi) {
const mid = lo + Math.ceil((hi - lo) / 2);
if (mid * (mid + 1) / 2 <= n) lo = mid; // doubles are exact far beyond 2^32
else hi = mid - 1;
}
return lo;
}fn solve(n: i64) -> i64 {
let (mut lo, mut hi) = (0i64, n); // the answer is in [lo, hi]
while lo < hi {
let mid = lo + (hi - lo + 1) / 2; // round up
if mid * (mid + 1) / 2 <= n { lo = mid } else { hi = mid - 1 }
}
lo
}solve :: Int -> Int
solve n = go 0 n
where
-- the answer is in [lo, hi]; mid rounds up
go lo hi
| lo >= hi = lo
| mid * (mid + 1) `div` 2 <= n = go mid hi
| otherwise = go lo (mid - 1)
where mid = lo + (hi - lo + 1) `div` 2Variants to try
- Each row needs twice as many coins as the row above: T(k) = 2ᵏ − 1, and the search (or a bit count) gives the answer.
- Find the smallest n for which there are exactly k complete rows: T(k), no search needed.
Next problems
Integer square root without a library
Search the candidates 0 to n for the last x with x² ≤ n, and keep the square from overflowing.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Easy10 minThe top of a mountain array
Nothing is sorted, but "is the next element smaller?" is false up the slope and true down it. Find the first true.
Open the problem →Write a solution and run it against the real test table.
Keep going
Integer square root without a library
Search the candidates 0 to n for the last x with x² ≤ n, and keep the square from overflowing.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Easy10 minThe top of a mountain array
Nothing is sorted, but "is the next element smaller?" is false up the slope and true down it. Find the first true.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.