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