# LeetCode 441: Arranging Coins

## Problem Restatement

We are given `n` coins.

We want to arrange them into a staircase shape.

The staircase must follow this rule:

| Row | Number of Coins |
|---|---:|
| 1st row | 1 |
| 2nd row | 2 |
| 3rd row | 3 |
| ... | ... |

Each row must contain exactly one more coin than the previous row.

We need to return the number of complete rows that can be formed.

The last row may be incomplete, and incomplete rows do not count.

The official problem asks for the number of complete staircase rows that can be formed using exactly `n` coins. ([leetcode.com](https://leetcode.com/problems/arranging-coins/))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Number of complete rows |
| Row sizes | `1, 2, 3, ...` |
| Incomplete row | Does not count |

Example function shape:

```python
def arrangeCoins(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 5
```

We build rows:

```text
row 1 -> 1 coin
row 2 -> 2 coins
row 3 -> needs 3 coins
```

After the first two rows:

```python
1 + 2 = 3
```

We have:

```python
5 - 3 = 2
```

coins left, which is not enough for row 3.

So the answer is:

```python
2
```

Example 2:

```python
n = 8
```

We build:

```python
1 + 2 + 3 = 6
```

Two coins remain:

```python
8 - 6 = 2
```

which is not enough for row 4.

Answer:

```python
3
```

Example 3:

```python
n = 1
```

We can build one row:

```python
1
```

Answer:

```python
1
```

## First Thought: Simulate Row by Row

We can repeatedly subtract row sizes.

Start with:

```python
row = 1
```

Then:

```python
n -= row
row += 1
```

until we cannot build the next row.

This works.

However, the problem has a direct mathematical structure.

## Key Insight

To build `k` complete rows, we need:

```python
1 + 2 + 3 + ... + k
```

coins.

This sum is the triangular number formula:

$$
1+2+3+\cdots+k=\frac{k(k+1)}{2}
$$

So we need the largest integer `k` such that:

$$
\frac{k(k+1)}{2}\le n
$$

This is a monotonic condition:

| `k` | Coins Needed |
|---|---:|
| Larger `k` | Needs more coins |
| Smaller `k` | Needs fewer coins |

Because the condition changes only once from true to false, binary search works perfectly.

## Algorithm

Binary search on the answer.

The number of complete rows must lie between:

```python
0 and n
```

For a candidate `mid`, compute:

$$
\frac{mid(mid+1)}{2}
$$

If this value is less than or equal to `n`, then `mid` complete rows are possible.

Move right to search for a larger answer.

Otherwise, move left.

At the end, return the largest valid `k`.

## Correctness

For any integer `k`, the number of coins required to build `k` complete rows is:

$$
\frac{k(k+1)}{2}
$$

This value increases as `k` increases.

Therefore:

| Condition | Meaning |
|---|---|
| `required(k) <= n` | `k` rows are possible |
| `required(k) > n` | `k` rows are impossible |

So the set of valid `k` values forms a prefix:

```text
valid, valid, valid, ..., invalid, invalid
```

Binary search correctly finds the largest valid `k`.

Whenever the midpoint satisfies the inequality, the answer is at least that large, so searching right preserves correctness.

Whenever the midpoint fails the inequality, the answer must be smaller, so searching left preserves correctness.

When the search ends, the returned value is the maximum number of complete rows that can be formed.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(log n)` | Binary search halves the range each step |
| Space | `O(1)` | Only a few variables are used |

## Implementation

```python
class Solution:
    def arrangeCoins(self, n: int) -> int:
        left = 0
        right = n

        while left <= right:
            mid = (left + right) // 2

            coins_needed = mid * (mid + 1) // 2

            if coins_needed <= n:
                left = mid + 1
            else:
                right = mid - 1

        return right
```

## Code Explanation

We search between:

```python
left = 0
right = n
```

The midpoint candidate is:

```python
mid = (left + right) // 2
```

The number of coins needed for `mid` rows is:

$$
\frac{mid(mid+1)}{2}
$$

implemented as:

```python
coins_needed = mid * (mid + 1) // 2
```

If enough coins exist:

```python
if coins_needed <= n:
```

then `mid` is valid, and we try larger values:

```python
left = mid + 1
```

Otherwise, `mid` is too large:

```python
right = mid - 1
```

When the loop finishes, `right` stores the largest valid row count.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.arrangeCoins(1) == 1

    assert s.arrangeCoins(5) == 2

    assert s.arrangeCoins(8) == 3

    assert s.arrangeCoins(3) == 2

    assert s.arrangeCoins(6) == 3

    assert s.arrangeCoins(10) == 4

    assert s.arrangeCoins(0) == 0

    assert s.arrangeCoins(2147483647) == 65535

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `1` | Smallest non-zero case |
| `5` | Incomplete third row |
| `8` | Standard example |
| `3` | Exact triangular number |
| `6` | Exact larger triangular number |
| `10` | Another exact staircase |
| `0` | No coins |
| Large input | Checks overflow safety and efficiency |