Description#
You have n
coins and you want to build a staircase with these coins. The staircase consists of k
rows where the ith
row has exactly i
coins. The last row of the staircase may be incomplete.
Given the integer n
, return the number of complete rows of the staircase you will build.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/0441.Arranging%20Coins/images/arrangecoins1-grid.jpg)
Input: n = 5
Output: 2
Explanation: Because the 3rd row is incomplete, we return 2.
Example 2:
![](https://spcdn.pages.dev/leetcode/problems/0441.Arranging%20Coins/images/arrangecoins2-grid.jpg)
Input: n = 8
Output: 3
Explanation: Because the 4th row is incomplete, we return 3.
Constraints:
Solutions#
Solution 1#
1
2
3
| class Solution:
def arrangeCoins(self, n: int) -> int:
return int(math.sqrt(2) * math.sqrt(n + 0.125) - 0.5)
|
1
2
3
4
5
| class Solution {
public int arrangeCoins(int n) {
return (int) (Math.sqrt(2) * Math.sqrt(n + 0.125) - 0.5);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| using LL = long;
class Solution {
public:
int arrangeCoins(int n) {
LL left = 1, right = n;
while (left < right) {
LL mid = left + right + 1 >> 1;
LL s = (1 + mid) * mid >> 1;
if (n < s)
right = mid - 1;
else
left = mid;
}
return left;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| func arrangeCoins(n int) int {
left, right := 1, n
for left < right {
mid := (left + right + 1) >> 1
if (1+mid)*mid/2 <= n {
left = mid
} else {
right = mid - 1
}
}
return left
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
| class Solution:
def arrangeCoins(self, n: int) -> int:
left, right = 1, n
while left < right:
mid = (left + right + 1) >> 1
if (1 + mid) * mid // 2 <= n:
left = mid
else:
right = mid - 1
return left
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int arrangeCoins(int n) {
long left = 1, right = n;
while (left < right) {
long mid = (left + right + 1) >>> 1;
if ((1 + mid) * mid / 2 <= n) {
left = mid;
} else {
right = mid - 1;
}
}
return (int) left;
}
}
|