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> |
Output:
Height of pyramid is 3
Time Complexity: O(n * log n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
