# Arranging Coins
**Difficulty:** EASY
[External](https://leetcode.com/problems/arranging-coins)
Canonical: https://scaleengineer.com/dsa/problems/arranging-coins
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
---
## Problem
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:**

![](https://assets.glich.co/dsa/arranging-coins/image0.jpg) 

**Input:** n = 5
**Output:** 2
**Explanation:** Because the 3rd row is incomplete, we return 2.

**Example 2:**

![](https://assets.glich.co/dsa/arranging-coins/image1.jpg) 

**Input:** n = 8
**Output:** 3
**Explanation:** Because the 4th row is incomplete, we return 3.

**Constraints:**

* `1 <= n <= 231 - 1`

# Approaches
## Brute Force Simulation
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.
**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.
**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.
### Explanation
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.
```java
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;
    }
}
```
### Algorithm
- 1. Initialize `completeRows = 0` and `currentRow = 1`.
- 2. Start a loop that continues as long as `n >= currentRow`.
- 3. Inside the loop, subtract `currentRow` from `n`: `n = n - currentRow`.
- 4. Increment `completeRows`: `completeRows++`.
- 5. Increment `currentRow`: `currentRow++`.
- 6. After the loop terminates, return `completeRows`.

## Binary Search
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`.
**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.
**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`.
### Explanation
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.
```java
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;
    }
}
```
### Algorithm
- 1. Initialize `left = 1`, `right = n`, and `result = 0`.
- 2. While `left <= right`:
- 3. Calculate `mid = left + (right - left) / 2`. Use `long` to prevent overflow.
- 4. Calculate the coins needed for `mid` rows: `coinsNeeded = mid * (mid + 1) / 2`.
- 5. If `coinsNeeded <= n`:
    - `mid` is a potential answer. Store it: `result = mid`.
    - Search for a larger `k`: `left = mid + 1`.
- 6. Else (`coinsNeeded > n`):
    - `mid` is too large. Search for a smaller `k`: `right = mid - 1`.
- 7. Return `result`.

## Mathematical Formula
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.
**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.
**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.sqrt` is generally reliable for standard integer ranges.
### Explanation
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.
```java
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);
    }
}
```
### Algorithm
- 1. Convert `n` to a `long` to avoid overflow in the next step.
- 2. Calculate `1 + 8 * n`.
- 3. Compute the square root of the result.
- 4. Subtract 1 from the square root.
- 5. Divide the result by 2.
- 6. The answer is the integer part of this final value. Casting to `int` will achieve this.

# Solutions
### Java

```java
class Solution { public int arrangeCoins ( int n ) { return ( int ) ( Math . sqrt ( 2 ) * Math . sqrt ( n + 0.125 ) - 0.5 ); } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
class Solution : def arrangeCoins ( self , n : int ) -> int : return int ( math . sqrt ( 2 ) * math . sqrt ( n + 0.125 ) - 0.5 )
```