0441. Arranging Coins

# 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 个硬币，按照递增的方式排列搭楼梯，第一层一个，第二层二个，……第 n 层需要 n 个硬币。问硬币 n 能够搭建到第几层？
• 这一题有 2 种解法，第一种解法就是解方程求出 X，`(1+x)x/2 = n`，即 `x = floor(sqrt(2*n+1/4) - 1/2)`，第二种解法是模拟。

## 代码 #

``````
package leetcode

import "math"

// 解法一 数学公式
func arrangeCoins(n int) int {
if n <= 0 {
return 0
}
x := math.Sqrt(2*float64(n)+0.25) - 0.5
return int(x)
}

// 解法二 模拟
func arrangeCoins1(n int) int {
k := 1
for n >= k {
n -= k
k++
}
return k - 1
}

``````

Apr 8, 2023