# LeetCode-Alg-441-Arranging-Coins

## LeetCode-Alg-441-Arranging-Coins

Posted by Jae on February 20, 2019

### 1、题目

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.


### 3、实现

public int arrangeCoins(int n) {
if (n < 1)
{
return 0;
}

int low = 1;
int high = n;

while (low <= high)
{
int mid = low + (high - low) / 2;
long sum = (long) mid*(1 + mid)/2;  // 使用等差数列求和公式可能造成溢出
if (sum == n)
{
return mid;
}else if (sum > n)
{
if (sum - mid < n)
{
return mid - 1;
}else
{
high = mid;
}
}else if (sum < n)
{
if (sum + (mid + 1) > n)
{
return mid;
}else
{
low = mid;
}
}
}

throw null;
}


### 4、方法二

public int arrangeCoins2(int n) {
if (n < 1)
{
return 0;
}

int line = 1;
n -= line;
while (n >= line+1)
{
line++;
n -= line;
}

return line;
}


### 5、方法三

public int arrangeCoins3(int n) {
if (n < 1)
{
return 0;
}
// 注意这里n*8该操作可能导致溢出
return (int) (-1 + Math.sqrt(1+8*(long)n)) / 2;
}