Dada una array, necesitamos encontrar la altura máxima del triángulo que podemos formar, a partir de los valores de la array, de modo que cada (i+1) nivel contenga más elementos con la suma mayor del nivel anterior.
Ejemplos:
Input : a = { 40, 100, 20, 30 }
Output : 2
Explanation : We can have 100 and 20 at the bottom level and either 40 or 30 at the upper level of the pyramid
Input : a = { 20, 20, 10, 10, 5, 2 }
Output : 3
Primero, de un vistazo, parece que tenemos que mirar los valores de la array. Pero no es así. Esta es la parte difícil de este problema. Aquí no tenemos que preocuparnos por los valores de la array porque podemos organizar cualquier elemento de la array en el valor triangular que satisfaga estas condiciones. Incluso si todos los elementos son iguales como array = {3,, 3, 3, 3, 3}, podemos tener una solución. Podemos colocar dos 3 en la parte inferior y un 3 en la parte superior o tres 3 en la parte inferior y dos 3 en la parte superior. Puede tomar cualquier ejemplo propio y siempre encontrará una solución para organizarlos en una configuración. Entonces, si nuestra altura máxima será 2, entonces deberíamos tener al menos 2 elementos en la parte inferior y un elemento en la parte superior, lo que significa que deberíamos tener un mínimo de 3 elementos (2*(2+1)/2). De manera similar, para 3 como altura, deberíamos tener un mínimo de 6 elementos en la array.
Por lo tanto, nuestra solución final simplemente se basa en la lógica de que si tenemos la altura máxima h posible para nuestra pirámide, entonces (h*(h+1))/2 elementos deben estar presentes en la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the maximum height
// of Pyramidal Arrangement of array values
#include <bits/stdc++.h>
using namespace std;
int MaximumHeight(int a[], int n)
{
int result = 1;
for (int i = 1; i <= n; ++i) {
// Just checking whether ith level
// is possible or not if possible
// then we must have atleast
// (i*(i+1))/2 elements in the
// array
long long y = (i * (i + 1)) / 2;
// updating the result value
// each time
if (y < n)
result = i;
// otherwise we have exceeded n value
else
break;
}
return result;
}
int main()
{
int arr[] = { 40, 100, 20, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << MaximumHeight(arr, n);
return 0;
}
Java
// Java program to find
// the maximum height of
// Pyramidal Arrangement
// of array values
import java.io.*;
class GFG
{
static int MaximumHeight(int []a,
int n)
{
int result = 1;
for (int i = 1; i <= n; ++i)
{
// Just checking whether
// ith level is possible
// or not if possible then
// we must have atleast
// (i*(i+1))/2 elements
// in the array
int y = (i * (i + 1)) / 2;
// updating the result
// value each time
if (y < n)
result = i;
// otherwise we have
// exceeded n value
else
break;
}
return result;
}
// Driver Code
public static void main (String[] args)
{
int []arr = { 40, 100, 20, 30 };
int n = arr.length;
System.out.println(MaximumHeight(arr, n));
}
}
// This code is contributed by ajit
Python3
# Python program to find the # maximum height of Pyramidal # Arrangement of array values def MaximumHeight(a, n): result = 1 for i in range(1, n): # Just checking whether ith level # is possible or not if possible # then we must have atleast # (i*(i+1))/2 elements in the array y = (i * (i + 1)) / 2 # updating the result # value each time if(y < n): result = i # otherwise we have # exceeded n value else: break return result # Driver Code arr = [40, 100, 20, 30] n = len(arr) print(MaximumHeight(arr, n)) # This code is contributed by # Sanjit_Prasad
C#
// C# program to find
// the maximum height of
// Pyramidal Arrangement
// of array values
using System;
class GFG
{
static int MaximumHeight(int []a,
int n)
{
int result = 1;
for (int i = 1; i <= n; ++i)
{
// Just checking whether
// ith level is possible
// or not if possible then
// we must have atleast
// (i*(i+1))/2 elements
// in the array
int y = (i * (i + 1)) / 2;
// updating the result
// value each time
if (y < n)
result = i;
// otherwise we have
// exceeded n value
else
break;
}
return result;
}
// Driver Code
static public void Main ()
{
int []arr = {40, 100, 20, 30};
int n = arr.Length;
Console.WriteLine(MaximumHeight(arr, n));
}
}
// This code is contributed
// by m_kit
PHP
<?php
// PHP program to find the maximum height
// of Pyramidal Arrangement of array values
function MaximumHeight($a, $n)
{
$result = 1;
for ($i = 1; $i <= $n; ++$i)
{
// Just checking whether ith level
// is possible or not if possible
// then we must have atleast
// (i*(i+1))/2 elements in the
// array
$y = ($i * ($i + 1)) / 2;
// updating the result value
// each time
if ($y < $n)
$result = $i;
// otherwise we have
// exceeded n value
else
break;
}
return $result;
}
// Driver Code
$arr = array(40, 100, 20, 30);
$n = count($arr);
echo MaximumHeight($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find
// the maximum height of
// Pyramidal Arrangement
// of array values
function MaximumHeight( a ,n)
{
let result = 1;
for ( i = 1; i <= n; ++i) {
// Just checking whether
// ith level is possible
// or not if possible then
// we must have atleast
// (i*(i+1))/2 elements
// in the array
let y = (i * (i + 1)) / 2;
// updating the result
// value each time
if (y < n)
result = i;
// otherwise we have
// exceeded n value
else
break;
}
return result;
}
// Driver Code
let arr = [ 40, 100, 20, 30 ];
let n = arr.length;
document.write(MaximumHeight(arr, n));
// This code is contributed by Rajput-Ji
</script>
2
Complejidad de tiempo: O(n)
Complejidad de espacio: O(1)
Podemos resolver este problema en O(1) tiempo. Simplemente necesitamos encontrar el máximo i tal que i*(i+1)/2 <= n . Si resolvemos la ecuación, obtenemos piso((-1+sqrt(1+(8*n)))/2)
C++
// CPP program to find the maximum height
// of Pyramidal Arrangement of array values
#include <bits/stdc++.h>
using namespace std;
int MaximumHeight(int a[], int n)
{
return floor((-1+sqrt(1+(8*n)))/2);
}
int main()
{
int arr[] = { 40, 100, 20, 30 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << MaximumHeight(arr, n);
return 0;
}
Java
// Java program to find the maximum height
// of Pyramidal Arrangement of array values
import java.lang.*;
class GFG {
static int MaximumHeight(int a[], int n)
{
return (int)Math.floor((-1 +
Math.sqrt(1 + (8 * n))) / 2);
}
public static void main(String[] args)
{
int arr[] = new int[]{ 40, 100, 20, 30 };
int n = arr.length;
System.out.println(MaximumHeight(arr, n));
}
}
// This code is contributed by Smitha
Python3
# Python program to find the # maximum height of Pyramidal # Arrangement of array values import math def MaximumHeight(a, n): return (-1 + int(math.sqrt(1 + (8 * n)))) // 2 # Driver Code arr = [40, 100, 20, 30] n = len(arr) print(MaximumHeight(arr, n)) # This code is contributed by # Sanjit_Prasad
C#
// C# program to find the maximum height
// of Pyramidal Arrangement of array values
using System;
class GFG {
static int MaximumHeight(int[]a, int n)
{
return (int)Math.Floor((-1 +
Math.Sqrt(1 + (8 * n))) / 2);
}
public static void Main()
{
int []arr = new int[]{ 40, 100, 20, 30 };
int n = 4;
Console.Write(MaximumHeight(arr, n));
}
}
// This code is contributed by Smitha
PHP
<?php
// PHP program to find
// the maximum height
// of Pyramidal Arrangement
// of array values
function MaximumHeight( $a, $n)
{
return floor((-1 + sqrt(1 +
(8 * $n))) / 2);
}
// Driver Code
$arr = array(40, 100, 20, 30);
$n = count($arr);
echo MaximumHeight($arr, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// javascript program to find the maximum height
// of Pyramidal Arrangement of array values
function MaximumHeight(a, n)
{
return Math.floor((-1 + Math.sqrt(1 + (8 * n))) / 2);
}
// Driver code
let arr = [ 40, 100, 20, 30 ];
let n = arr.length;
document.write(MaximumHeight(arr, n));
// This code is contributed by gauravrajput1
</script>
2
Complejidad de tiempo: O(1)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA