Arranging Coins
EasyPrompt
You have n coins and you want to build a staircase with these coins. The staircase consists of k rows where the ith row has exactly i coins. The last row of the staircase may be incomplete.
Given the integer n, return the number of complete rows of the staircase you will build.
Example 1:
Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.Example 2:
Input: n = 8
Output: 3
Explanation: Because the 4th row is incomplete, we return 3.
Constraints:
1 <= n <= 231 - 1
Approaches
3 approaches with complexity analysis and trade-offs.
A more efficient approach is to use binary search. We know that the number of coins required for k complete rows is 1 + 2 + ... + k = k * (k + 1) / 2. This is a monotonically increasing function of k. We can use binary search to find the largest k for which this sum is less than or equal to n.
Algorithm
-
- Initialize
left = 1,right = n, andresult = 0.
- Initialize
-
- While
left <= right:
- While
-
- Calculate
mid = left + (right - left) / 2. Uselongto prevent overflow.
- Calculate
-
- Calculate the coins needed for
midrows:coinsNeeded = mid * (mid + 1) / 2.
- Calculate the coins needed for
-
- If
coinsNeeded <= n:
midis a potential answer. Store it:result = mid.- Search for a larger
k:left = mid + 1.
- If
-
- Else (
coinsNeeded > n):
midis too large. Search for a smallerk:right = mid - 1.
- Else (
-
- Return
result.
- Return
Walkthrough
The problem asks for the largest integer k such that the sum of coins S_k = k * (k + 1) / 2 does not exceed n. Since S_k increases as k increases, we can efficiently search for k in the range [1, n]. We set up a binary search with left and right pointers. For each mid value, we calculate the coins needed, mid * (mid + 1) / 2. If the coins needed are less than or equal to n, it means mid could be our answer, and we should try for a larger k. So, we record mid and move our search to the right half (left = mid + 1). If the coins needed are more than n, mid is too large, and we must search in the left half (right = mid - 1). It's crucial to use long for intermediate calculations to avoid integer overflow, as n can be large.
class Solution { public int arrangeCoins(int n) { long left = 1, right = n; long result = 0; while (left <= right) { long mid = left + (right - left) / 2; long coinsNeeded = mid * (mid + 1) / 2; if (coinsNeeded <= n) { result = mid; left = mid + 1; } else { right = mid - 1; } } return (int) result; }}Complexity
Time
O(log n). The binary search algorithm halves the search space in each iteration. The search space is from 1 to `n`.
Space
O(1). We only use a constant number of variables for the binary search pointers and result.
Trade-offs
Pros
Significantly faster than the brute-force approach.
Guaranteed to find the solution within logarithmic time.
Cons
Slightly more complex to implement than the linear scan.
Requires careful handling of potential integer overflows by using
long.
This approach simulates the process of building the staircase row by row. We start with the first row, which requires 1 coin, then the second row, which requires 2 coins, and so on. We keep track of the number of complete rows we can build until we run out of coins.
Algorithm
-
- Initialize
completeRows = 0andcurrentRow = 1.
- Initialize
-
- Start a loop that continues as long as
n >= currentRow.
- Start a loop that continues as long as
-
- Inside the loop, subtract
currentRowfromn:n = n - currentRow.
- Inside the loop, subtract
-
- Increment
completeRows:completeRows++.
- Increment
-
- Increment
currentRow:currentRow++.
- Increment
-
- After the loop terminates, return
completeRows.
- After the loop terminates, return
Walkthrough
We can solve this problem by iteratively subtracting the number of coins required for each row from the total number of coins n. We use a loop that starts from row 1 and goes up. In each iteration, we check if we have enough coins to build the current row.
If we have enough coins (i.e., n >= current_row_number), we subtract the coins for that row from n and increment our count of complete rows.
We continue this process until we don't have enough coins for the current row. The final count of complete rows is our answer.
class Solution { public int arrangeCoins(int n) { int k = 0; // Number of complete rows int i = 1; // Current row number while (n >= i) { n -= i; k++; i++; } return k; }}Complexity
Time
O(sqrt(n)). The loop runs `k` times, where `k` is the number of complete rows. The total number of coins for `k` rows is `k * (k + 1) / 2 ≈ n`. This implies `k^2 ≈ 2n`, so `k` is proportional to `sqrt(n)`. Therefore, the time complexity is O(sqrt(n)).
Space
O(1). We only use a few variables to store the count and the current row number, so the space used is constant.
Trade-offs
Pros
Simple to understand and implement.
Requires no advanced mathematical knowledge.
Cons
Inefficient for large values of
n.Can lead to a 'Time Limit Exceeded' error on platforms with strict time limits.
The most efficient approach involves solving a mathematical inequality. The problem is to find the largest integer k such that k * (k + 1) / 2 <= n. This can be rewritten as a quadratic inequality k^2 + k - 2n <= 0. We can solve for k using the quadratic formula.
Algorithm
-
- Convert
nto alongto avoid overflow in the next step.
- Convert
-
- Calculate
1 + 8 * n.
- Calculate
-
- Compute the square root of the result.
-
- Subtract 1 from the square root.
-
- Divide the result by 2.
-
- The answer is the integer part of this final value. Casting to
intwill achieve this.
- The answer is the integer part of this final value. Casting to
Walkthrough
We need to find the maximum integer k that satisfies the inequality k * (k + 1) / 2 <= n.
Let's rearrange the inequality:
k^2 + k <= 2n
k^2 + k - 2n <= 0
We can find the positive root of the corresponding equation x^2 + x - 2n = 0 using the quadratic formula: x = (-b ± sqrt(b^2 - 4ac)) / 2a.
Here, a=1, b=1, c=-2n. The positive root is x = (-1 + sqrt(1 - 4(1)(-2n))) / 2 = (-1 + sqrt(1 + 8n)) / 2.
The largest integer k satisfying the inequality is the floor of this positive root.
The implementation involves calculating this formula. We must use long for 8 * n to prevent overflow and double for the square root operation.
class Solution { public int arrangeCoins(int n) { // We need to find k such that k * (k + 1) / 2 <= n // k^2 + k - 2n <= 0 // Using quadratic formula, the positive root is (-1 + sqrt(1 + 8n)) / 2 // We must use long for 8*n to avoid overflow. return (int) ((-1 + Math.sqrt(1 + 8L * n)) / 2); }}Complexity
Time
O(1). The solution involves a fixed number of arithmetic operations and a square root function, which can be considered constant time.
Space
O(1). No extra space is used besides a few variables for the calculation.
Trade-offs
Pros
Extremely fast, providing a constant time solution.
Elegant and concise.
Cons
Requires understanding the underlying mathematical relationship and solving a quadratic inequality.
Potential for floating-point precision issues, although
Math.sqrtis generally reliable for standard integer ranges.
Solutions
Solution
class Solution { public int arrangeCoins ( int n ) { return ( int ) ( Math . sqrt ( 2 ) * Math . sqrt ( n + 0.125 ) - 0.5 ); } }using LL = long ; class Solution { public: int arrangeCoins ( int n ) { LL left = 1 , right = n ; while ( left < right ) { LL mid = left + right + 1 >> 1 ; LL s = ( 1 + mid ) * mid >> 1 ; if ( n < s ) right = mid - 1 ; else left = mid ; } return left ; } };class Solution : def arrangeCoins ( self , n : int ) -> int : return int ( math . sqrt ( 2 ) * math . sqrt ( n + 0.125 ) - 0.5 )Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.