Given an array of rectangular blocks with dimensions {l, b} of length m. we can shape each rectangular block into a single square block by trimming either one of its dimensions or both. With these square blocks, a pyramid is formed. Our task is to find the maximum height of the pyramid that can be formed.
Note:
A pyramid is built by placing a square block, say N * N, at the base, placing another square block N-1 * N-1 on top of that, a square block of N-2 * N-2 on top of that, and so on, ending with a 1*1 block on top. The height of such a pyramid is N.
Examples:
Input: n = 4, arr[] = {{8, 8}, {2, 8}, {4, 2}, {2, 1}}
Output: Height of pyramid is 3
Explanation:
{8, 8} blocks can be trimmed to {3, 3}
{2, 8} block can be trimmed to {2, 2} or {4, 2} block can be trimmed to {2, 2}
{2, 1} block can be trimmed to {1, 1}
so the height of the pyramid is 3Input: n = 5, arr[] = {{9, 8}, {7, 4}, {8, 1}, {4, 4}, {2, 1}}
Output: Height of pyramid is 4
Approach:
- We have to make dimensions for every block as
l * l or b * b
- Since we can only trim but not join, we choose the dimensions of the square block as min(l, b)
- Create an array a with the MIN(l, b) on every rectangular block
- sort the array a and initialize the height to 0
- Traverse through array a if the element in the array is greater than height + 1
then increment the value of height by 1. - return height
C++
#include <bits/stdc++.h>#include <iostream>using namespace std;// Function to return// The height of pyramidint pyramid(int n, int arr[][2]){ vector<int> a; int height = 0; for (int i = 0; i < n; i++) { // For every ith array // append the minimum value // between two elements a.push_back(min(arr[i][0], arr[i][1])); } sort(a.begin(), a.end()); for (int i = 0; i < a.size(); i++) { // if the element in array is // greater than height then // increment the value the // value of height by 1 if (a[i] > height) height++; } return height;}// Driver codeint main(){ int n = 4; int arr[][2] = { { 8, 8 }, { 8, 2 }, { 4, 2 }, { 2, 1 } }; cout << "Height of pyramid is " << pyramid(n, arr);} |
Java
import java.util.*;public class Gfg { static int pyramid(int n, int arr[][]) { int[] a = new int[n]; int height = 0; for (int i = 0; i < n; i++) { // For every ith array // append the minimum value // between two elements a[i] = arr[i][0] < arr[i][1] ? arr[i][0] : arr[i][1]; } // sorting the array Arrays.sort(a); for (int i = 0; i < n; i++) { // if the element in array is // greater than height then // increment the value the // value of height by 1 if (a[i] > height) height++; } return height; } public static void main(String[] args) { int n = 4; int arr[][] = { { 8, 8 }, { 8, 2 }, { 4, 2 }, { 2, 1 } }; System.out.println("Height of pyramid is " + pyramid(n, arr)); }} |
Python
# Function to return# The height of pyramiddef pyramid(n, arr): # Empty array a = [] height = 0 for i in arr: # For every ith array # append the minimum value # between two elements a.append(min(i)) # Sort the array a.sort() # Traverse through the array a for i in range(len(a)): # if the element in array is # greater than height then # increment the value the # value of height by 1 if a[i] > height: height = height + 1 return height# Driver codeif __name__ == '__main__': n = 4 arr = [[8, 8], [2, 8], [4, 2], [2, 1]] print("Height of pyramid is", pyramid(n, arr)) |
C#
using System;class Gfg { static int pyramid(int n, int [,]arr) { int[] a = new int[n]; int height = 0; for (int i = 0; i < n; i++) { // For every ith array // append the minimum value // between two elements a[i] = arr[i, 0] < arr[i, 1] ? arr[i, 0] : arr[i, 1]; } // sorting the array Array.Sort(a); for (int i = 0; i < n; i++) { // if the element in array is // greater than height then // increment the value the // value of height by 1 if (a[i] > height) height++; } return height; } // Driver code public static void Main() { int n = 4; int [,]arr = { { 8, 8 }, { 8, 2 }, { 4, 2 }, { 2, 1 } }; Console.WriteLine("Height of pyramid is " + pyramid(n, arr)); } } // This code is contributed by AnkitRai01 |
Javascript
<script>// Function to return// The height of pyramidfunction pyramid(n, arr) { let a = new Array(); let height = 0; for (let i = 0; i < n; i++) { // For every ith array // append the minimum value // between two elements a.push(Math.min(arr[i][0], arr[i][1])); } a.sort((a, b) => a - b); for (let i = 0; i < a.length; i++) { // if the element in array is // greater than height then // increment the value the // value of height by 1 if (a[i] > height) height++; } return height;}// Driver codelet n = 4;let arr = [[8, 8],[8, 2],[4, 2],[2, 1]];document.write("Height of pyramid is " + pyramid(n, arr));</script> |
Height of pyramid is 3
Time Complexity: O(n * log n)
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
