Altura máxima cuando las monedas están dispuestas en triángulo

Tenemos N monedas que deben organizarse en forma de triángulo, es decir, la primera fila tendrá 1 moneda, la segunda fila tendrá 2 monedas y así sucesivamente, necesitamos decir la altura máxima que podemos lograr usando estas N monedas.
Ejemplos: 
 

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.

Este problema se puede resolver encontrando una relación entre la altura del triángulo y el número de monedas. Deje que la altura máxima sea H, entonces la suma total de la moneda debe ser menor que 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

El siguiente código se implementa en el concepto mencionado anteriormente, 
 

//  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 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 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# 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 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.
?>

<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>

Producción: 
 

4

Complejidad del tiempo: O(sqrt(n))

Espacio auxiliar: O(1)

Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.