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:

1
2
3
4
5
6
7
8
n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2.

Example 2:

1
2
3
4
5
6
7
8
9
n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.

根据等差数列求和公式, 设步数为x, 那么 x * (x + 1) / 2 <= n. 结果为满足不等式的最大的x. x的范围是[1, n], 可以用二分查找实现.

代码如下:
要处理溢出的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int arrangeCoins(int n) {
    if (n <= 0)
        return 0;
    int left = 1, right = n;
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        long x = (long) mid * (mid + 1);
        if (x / 2 < n) {
            left = mid;
        } else if (x / 2 >= n) {
            right = mid;
        }
    }
    if ((long) right * (right + 1) / 2 <= n)
        return right;
    return left;
}

Math

求满足 $x^2 + x - 2 * n <= 0$ 的最大的x. 二元一次方程有两个解, 这里较大的解即为所求. $x = \frac{-b + \sqrt{b^2 - 4ac}}{2a}$

1
2
3
4
5
public int arrangeCoins(int n) {
    if (n <= 0)
        return 0;
    return (-1 + (int) Math.sqrt(1 + (long) 8 * n)) / 2;
}