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个硬币在一个特定的盒子里，现在要你拿出硬币按照指定的规则进行放置。规则如下：第一行放1枚硬币，第二行放2枚硬币，一次类推，第m行放置m个硬币。n为正整数，如果你能把硬币按照规则完全放满。满足，第m行有m个硬币。那么返回最后一行m的值 否则返回m-1 的值 例： n == 5
你可以这样放置： 第一行：1个 第二行：2个 第三行：2个(2<3) 没放满，不满足题意，故返回2

n == 10
你可以这样放置： 第一行：1个 第二行：2个 第三行：3个 第四行：4个(4=4) 放满，满足题意，刚好放完，故返回4

分析：

1.我们可以采取暴力的方法，每放1行 减去每行对应数目的硬币。如果刚好放得下，返回最后一行的行数。如果放不下，放回上一行的行数。

复杂度分析：

时间复杂度O(n)

Java：

class Solution {  
    public int arrangeCoins(int n) {
        int i = 1, sub = n - 1;
        while (sub >= i + 1) {
            i++;
            sub -= i;
        }
        return i;
    }
}

C++:

class Solution {  
public:  
    int arrangeCoins(int n) {
         if (n == 0) {  
            return 0;  
        }  
        int i = 1, r = n;  
         while (r > i + 1) {
            i++;
            r -= i;
        }
               return i;
    } 

};

Swift:

class Solution {  
    func arrangeCoins(_ n: Int) -> Int {
          var n = n
    for i in 1...Int.max {
        if n - i >= 0 {
            n -= i
        } else {
            return i - 1
        }
    }
    return 0
    }
}

2.我们搜索前i行之和刚好大于n的临界(找中间的临界值 然后判断1+2+3+...+n的值进行比较)O(lgn)

class Solution {  
public:  
    int arrangeCoins(int n) {
         if (n == 0) {  
            return 0;  
        }  
        int l = 1, r = n;  
        while (l < r) {  
            long mid = l + (r - l + 1) / 2;  
            if (mid * (mid + 1) / 2.0 <= n) {  
                l = mid;  
            }  
            else if (mid * (mid + 1) / 2 > n) {  
                r = mid - 1;  
            }  
        }  
        return r;  
    } 
};

3.数学计算

根据等差数列求和公式计算 1+2+3+4+...+n
(1 + x) * x / 2 <= n

class Solution {  
    func arrangeCoins(_ n: Int) -> Int {
             return Int((sqrt(8 * Double(n) + 1) - 1) / Double(2))
    }
}

本题来自:leetCode