The problem is equivalent to math problem: find max integer k such that k(k+1) <= 2n. Then it is straightforward to use root formula of quadratic equation ax^2+bx+c = 0 which is

`r = (-b+/-sqrt(b^2-4ac))/2`

, where negative root is ignored.

However, the interesting part of this problem, I think, is how to handle overflow and numeric accuracy. The max value during the formula calculation is `8*n+1`

, where `n`

is `int`

type. If we do not use `(long)`

to get a higher overflow upper bound, I was trying to reformulate the expression as `1.5*sqrt(8*(n/9.0)+1.0/9.0)-0.5`

, which guarantees no overflow in `int`

range. However, this suffers loss of accuracy when the given `n`

happens to form a complete staircase (e.g., `n=6`

) and therefore gives off-by-1 results. Not sure whether we have other solutions using the formula without casting to `long`

. Any comment is appreciated!

```
int arrangeCoins(int n) {
return (int)(0.5*(sqrt(8*(long)n+1)-1));
}
```