Algorithm
Problem Name: 441. Arranging Coins
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:
Input: n = 5 Output: 2 Explanation: Because the 3rd row is incomplete, we return 2.
Example 2:
Input: n = 8 Output: 3 Explanation: Because the 4th row is incomplete, we return 3.
Constraints:
1 <= n <= 231 - 1
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int arrangeCoins(int n) {
int i = 1;
while(n >= i) n -= i, i++;
return i - 1;
}
};
class Solution {
public:
int arrangeCoins(int n) {
return floor(-0.5+sqrt((double)2*n+0.25));
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int arrangeCoins(int n) {
long left = 1;
long right = n;
while (left < = right) {
long mid = (left + right) / 2;
long sum = mid * (mid + 1) / 2;
if (sum == n) {
return (int) mid;
} else if (sum > n) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return (int) right;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const arrangeCoins = function(n) {
if (n === 0) {
return 0
}
let num = 1
let sum = 1
while(n >= sum + num + 1) {
num += 1
sum += num
}
return num
};
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def arrangeCoins(self, n: int) -> int:
sm = res = 0
for i in range(1, n + 1):
sm += i
if sm > n:
break
res += 1
return res
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0441_ArrangingCoins
{
public int ArrangeCoins(int n)
{
return (int)(Math.Sqrt(2 * (long)n + 0.25) - 0.5);
}
}
}
Input
Output