# 441. Arranging Coins

[ **441. Arranging Coins**](https://leetcode.com/problemset/all/?search=441)

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly kcoins.

Given n, find the total number of **full** staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

**Example 1:**

```
n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.
```

**Example 2:**

```
n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.
```

***My Solutions:***

方法1：naive的方法，一层一层加

```
class Solution {
    public int arrangeCoins(int n) {
        if (n < 0) return -1;
        if (n == 0) return 0;
        if (n == 1) return 1;
        int row = 1;
        long sum = 1;
        while (sum + row + 1 <= n) {
            row++;
            sum += row;
        }
        return row;
    }
}
```

方法2：数学方法

累加和的公式为：sum = (1+x)\*x/2

sum <= n ，反过来求层数x。如果直接开方来求会存在错误，必须因式分解求得准确的x值：

(1+x)\*x/2 <= n \
x + x\*x <= 2\*n \
4\*x\*x + 4\*x <= 8\*n \
(2\*x + 1)\*(2\*x + 1) - 1 <= 8\*n \
x <= (sqrt(8\*n + 1) - 1) / 2

最后强制转换为int型数

```
public int arrangeCoins(int n) {
    return (int)((-1 + Math.sqrt(1 + 8 * (long) n)) / 2);
}
```