Maximum height when coins are arranged in a triangle - GeeksforGeeks
We have N coins which need to arrange in form of a triangle, i.e. first row will have 1 coin, second row will have 2 coins and so on, we need to tell maximum height which we can achieve by using these N coins.
Read full article from Maximum height when coins are arranged in a triangle - GeeksforGeeks
We have N coins which need to arrange in form of a triangle, i.e. first row will have 1 coin, second row will have 2 coins and so on, we need to tell maximum height which we can achieve by using these N coins.
This problem can be solved by finding a relation between height of the triangle and number of coins. Let maximum height is H, then total sum of coin should be less than N,
Sum of coins for height H <= N H*(H + 1)/2 <= N H*H + H – 2*N <= 0 Now by Quadratic formula (ignoring negative root) Maximum H can be (-1 + √(1 + 8N)) / 2 Now we just need to find the square root of (1 + 8N) for which we can use Babylonian method of finding square root
/* Returns the square root of n. Note that the function */
float
squareRoot(
float
n)
{
/* We are using n itself as initial approximation
This can definitely be improved */
float
x = n;
float
y = 1;
float
e = 0.000001;
/* e decides the accuracy level*/
while
(x - y > e)
{
x = (x + y) / 2;
y = n/x;
}
return
x;
}
// Method to find maximum height of arrangement of coins
int
findMaximumHeight(
int
N)
{
// calculating portion inside the square root
int
n = 1 + 8*N;
int
maxH = (-1 + squareRoot(n)) / 2;
return
maxH;
}