## 题目描述：

LeetCode 441. 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.

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

## 题目大意：

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

## 解题思路：

`x ^ 2 + x = 2 * n`

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

## Python代码：

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

## Python代码：

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

## Python代码：

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

Pingbacks已关闭。

1. y119777 发布于 2016年10月30日 17:05 #

问一下，一般二分怎么写，我老是不能掌控+1和-1和while条件，有时候导致死循环，你又什么技巧么，谢谢

2. 在线疯狂 发布于 2016年10月30日 18:23 #

推荐一篇关于二分查找的文章：https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/

3. y119777 发布于 2016年10月30日 18:42 #

谢谢