Arranging Coins
You have nii
Example 1
Output: 2
Explanation: rows of 1 and 2 coins use 3 coins; the 2 coins left cannot fill row 3.
Example 2
Output: 3
Explanation: rows of 1, 2 and 3 coins use 6 coins; the 2 left cannot fill row 4.
How to Think About It
Step 1: Count the coins in k full rows
k complete rows use 1 + 2 + … + k coins. That sum has a closed form, k(k + 1) / 2
Step 2: Turn it into a search
The answer is the largest k with k(k + 1) / 2 <= n. As k grows, the coins needed only grow, so the test "do k rows fit?" is true for small k and false from some point on. Binary search finds the last true.
Step 3: Search for the last true without skipping it
- If
rows fit, mid might be the answer: keep it withmid .lo = mid - Otherwise mid is too many:
.hi = mid - 1
Because one branch sets lo = midmid = lo + (hi - lo + 1) / 2lo = 2
Step 4: Use long
For n near 231, mid * (mid + 1)intlong
Walkthrough
n = 8:
| lo | hi | mid (rounded up) | Coins for mid rows | Decision |
|---|---|---|---|---|
| 0 | 8 | 4 | 10 | more than 8: hi = 3 |
| 0 | 3 | 2 | 3 | fits: lo = 2 |
| 2 | 3 | 3 | 6 | fits: lo = 3 |
| 3 | 3 | lo == hi: answer 3 |
Java Solution
This is the last-true template: the midpoint rounds up so that lo = midlongmid * (mid + 1)
public class ArrangingCoins {
// Largest k with 1 + 2 + ... + k = k(k + 1) / 2 <= n
public static int arrangeCoins(int n) {
long lo = 0;
long hi = n;
while (lo < hi) {
long mid = lo + (hi - lo + 1) / 2; // round up, so lo = mid always makes progress
if (mid * (mid + 1) / 2 <= n) {
lo = mid; // mid full rows fit
} else {
hi = mid - 1;
}
}
return (int) lo;
}
public static void main(String[] args) {
System.out.println(arrangeCoins(5)); // 2
System.out.println(arrangeCoins(8)); // 3
System.out.println(arrangeCoins(2147483647)); // 65535
}
}
The original implementation, k(k + 1) / 2 = n(int) ((Math.sqrt(8.0 * n + 1) - 1) / 2)
Complexity
- Time: O(log n).
- Space: O(1).