Given an array, we need to find the maximum height of the triangle which we can form, from the array values such that every (i+1)th level contain more elements with the larger sum from the previous level.
Examples:
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 pyramidInput : a = { 20, 20, 10, 10, 5, 2 }
Output : 3
First, at a glance, it looks like that we may have to look at the array values. But it’s not so. This is the tricky part of this problem. Here we don’t have to care about the array values because we can arrange any elements of the array in the triangular value satisfying these condition. Even if all the elements are equal like array = { 3,, 3, 3, 3, 3}, we can have solution.
We can place two 3’s at the bottom and one 3’s at the top or three 3’s at the bottom and two 3’s at the top. You may take any example of your own and you will always find a solution of arranging them at a configuration. So, if our maximum height will be 2 then we should have at least 2 elements at the bottom and one element at the top, which means we should have minimum 3 elements (2*(2+1)/2). Similarly, for 3 as a height, we should have minimum 6 elements in the array.
Thus our final solution just lies on the logic that if we have maximum height h possible for our pyramid then (h*(h+1))/2 elements must be present in the array.
Implementation:
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 valuesimport 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 valuesdef 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 Codearr = [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 valuesusing 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 valuesfunction 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
Complexity Analysis:
- Time Complexity: O(n)
- Space Complexity: O(1)
Implementation: We can solve this problem in O(1) time. We simple need to find the maximum i such that i*(i+1)/2 <= n. If we solve the equation, we get floor((-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 valuesimport 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 valuesimport mathdef MaximumHeight(a, n): return (-1 + int(math.sqrt(1 + (8 * n)))) // 2# Driver Codearr = [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 valuesusing 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 valuesfunction 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 valuesfunction 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
Complexity Analysis:
- Time Complexity: O(logn) as it is using inbuilt sqrt function
- Space Complexity: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
