# 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.
``````

``````class Solution {
public:
int arrangeCoins(int n) {
int cur = 1, rem = n - 1;
while (rem >= cur + 1) {
++cur;
rem -= cur;
}
return n == 0 ? 0 : cur;
}
};
``````

``````class Solution {
public:
int arrangeCoins(int n) {
if (n <= 1) return n;
long low = 1, high = n;
while (low < high) {
long mid = low + (high - low) / 2;
if (mid * (mid + 1) / 2 <= n) low = mid + 1;
else high = mid;
}
return low - 1;
}
};
``````

``````class Solution {
public:
int arrangeCoins(int n) {
return (int)((-1 + sqrt(1 + 8 * (long)n)) / 2);
}
};
``````

https://discuss.leetcode.com/topic/65664/my-55ms-c-solution

https://discuss.leetcode.com/topic/65575/java-o-1-solution-math-problem

https://discuss.leetcode.com/topic/65631/c-three-solutions-o-n-o-logn-o-1/2

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation