## Saturday, November 12, 2016

### Maximum height when coins are arranged in a triangle - GeeksforGeeks

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
(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;`
`}`