# Arranging Coins

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

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

nis 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.
```

### 题目大意：

你有n枚硬币，想要组成一个阶梯形状，其中第k行放置k枚硬币。

给定n，计算可以形成的满阶梯的最大行数。

n是非负整数，并且在32位带符号整数范围之内。

### 解题思路：

**解法I 解一元二次方程（初等数学）：**

The problem is basically asking the maximum length of consecutive number that has the running sum lesser or equal to \`n\`. In other word, find \`x\` that satisfy the following condition:

\`1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + x <= n\`

\`sum\_{i=1}^x i <= n\`

Running sum can be simplified,

\`(x \* ( x + 1)) / 2 <= n\`

```
x ^ 2 + x = 2 * n
```

解得：

```
x = sqrt(2 * n + 1/4) - 1/2
```

```
class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        return int(math.sqrt(2 * n + 0.25) - 0.5)
```

注意：int(2.5)=2 所以当最后一行未放满的时候，返回上一行。

**解法II 二分枚举答案（Binary Search）：**

在上下界l, r = \[1, n]范围内用二分法寻找m，m就是行数

等差数列前m项和：1+2+3+4+...+m ＝ m \* (m + 1) / 2

三种情况

1. m \* (m + 1) / 2 == n
2. m \* (m + 1) / 2 < n
3. m \* (m + 1) / 2 > n

注意，当循环结束还没有找到等于n的数时，r\<l, 我们搜索前i行之和刚好大于n的临界点，这样我们减一个就是能排满的行数需要返回 (l-1)

```
class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        #return int(math.sqrt(2 * n + 0.25) - 0.5)
        l, r = 1, n
        while l <= r:
            m = (l + r) / 2
            if m * (m + 1) / 2 > n:
                r = m - 1
            elif m * (m + 1) / 2 == n:
                return m
            else:
                l = m + 1
        return l-1
```

## 二刷：

注意循环后的判断条件：

```
class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        start, end = 1, n
        while start+1 < end:
            mid = (start+end)/2
            if mid*(mid+1)/2 < n:
                start = mid
            else:
                end = mid
        if end*(end+1)/2<=n:
            return end
        return start
```
