Maximum height when coins are arranged in a triangle
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.
Examples:
Input : N = 7 Output : 3 Maximum height will be 3, putting 1, 2 and then 3 coins. It is not possible to use 1 coin left. Input : N = 12 Output : 4 Maximum height will be 4, putting 1, 2, 3 and 4 coins, it is not possible to make height as 5, because that will require 15 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
Below code is implemented on above stated concept,
CPP
// C++ program to find maximum height of arranged // coin triangle #include <bits/stdc++.h> using namespace std; /* 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; } // Driver code to test above method int main() { int N = 12; cout << findMaximumHeight(N) << endl; return 0; } |
Java
// Java program to find maximum height // of arranged coin triangle class GFG { /* Returns the square root of n. Note that the function */ static float squareRoot( float n) { /* We are using n itself as initial approximation.This can definitely be improved */ float x = n; float y = 1 ; // e decides the accuracy level float e = 0 .000001f; while (x - y > e) { x = (x + y) / 2 ; y = n / x; } return x; } // Method to find maximum height // of arrangement of coins static int findMaximumHeight( int N) { // calculating portion inside // the square root int n = 1 + 8 *N; int maxH = ( int )(- 1 + squareRoot(n)) / 2 ; return maxH; } // Driver code public static void main (String[] args) { int N = 12 ; System.out.print(findMaximumHeight(N)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find # maximum height of arranged # coin triangle # Returns the square root of n. # Note that the function def squareRoot(n): # We are using n itself as # initial approximation # This can definitely be improved x = n y = 1 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 def findMaximumHeight(N): # calculating portion inside the square root n = 1 + 8 * N maxH = ( - 1 + squareRoot(n)) / 2 return int (maxH) # Driver code to test above method N = 12 print (findMaximumHeight(N)) # This code is contributed by # Smitha Dinesh Semwal |
C#
// C# program to find maximum height // of arranged coin triangle using System; class GFG { /* Returns the square root of n. Note that the function */ static float squareRoot( float n) { /* We are using n itself as initial approximation.This can definitely be improved */ float x = n; float y = 1; // e decides the accuracy level float e = 0.000001f; while (x - y > e) { x = (x + y) / 2; y = n / x; } return x; } static int findMaximumHeight( int N) { // calculating portion inside // the square root int n = 1 + 8*N; int maxH = ( int )(-1 + squareRoot(n)) / 2; return maxH; } /* program to test above function */ public static void Main() { int N = 12; Console.Write(findMaximumHeight(N)); } } // This code is contributed by _omg |
PHP
<?php // PHP program to find maximum height // of arranged coin triangle /* Returns the square root of n. Note that the function */ function squareRoot( $n ) { /* We are using n itself as initial approximation This can definitely be improved */ $x = $n ; $y = 1; /* e decides the accuracy level*/ $e = 0.000001; while ( $x - $y > $e ) { $x = ( $x + $y ) / 2; $y = $n / $x ; } return $x ; } // Method to find maximum height of // arrangement of coins function findMaximumHeight( $N ) { // calculating portion inside // the square root $n = 1 + 8 * $N ; $maxH = (-1 + squareRoot( $n )) / 2; return floor ( $maxH ); } // Driver code to test above method $N = 12; echo findMaximumHeight( $N ) ; // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program to find maximum height // of arranged coin triangle /* Returns the square root of n. Note that the function */ function squareRoot(n) { /* We are using n itself as initial approximation.This can definitely be improved */ let x = n; let y = 1; // e decides the accuracy level let e = 0.000001; while (x - y > e) { x = (x + y) / 2; y = n / x; } return x; } // Method to find maximum height // of arrangement of coins function findMaximumHeight(N) { // calculating portion inside // the square root let n = 1 + 8*N; let maxH = (-1 + squareRoot(n)) / 2; return Math.round(maxH); } // Driver Code let N = 12; document.write(findMaximumHeight(N)); // This code is contributed by avijitmondal1998. </script> |
Output:
4
Time complexity: O(log(n))
Auxiliary space: O(1)