Area of the largest square that can be formed from the given length sticks using Hashing
Given an array arr[] of N integers representing the heights of the sticks. The task is to find the area of the largest square that can be formed using these sticks and the count of such squares. Note that a single side of the square can only use a single stick.
Examples:
Input: arr[] = {5, 3, 2, 3, 6, 3, 3}
Output:
Area = 9
Count = 1
Side of the square will be 3 and
only one such square is possible.
Input: arr[] = {2, 2, 2, 9, 2, 2, 2, 2, 2}
Output:
Area = 4
Count = 2
Approach: Count the frequencies of all the elements of the array. Now, starting from the maximum (in order to maximize the area) find the first frequency which is at least 4 so that a square can be formed then the area can be calculated as freq[i] * freq[i] and the count of such squares will be freq[i] / 4.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to find the area of the largest // square that can be formed // and the count of such squares void findMaxSquare( int arr[], int n) { // Maximum value from the array int maxVal = *max_element(arr, arr + n); // Update the frequencies of // the array elements int freq[maxVal + 1] = { 0 }; for ( int i = 0; i < n; i++) freq[arr[i]]++; // Starting from the maximum length sticks // in order to maximize the area for ( int i = maxVal; i > 0; i--) { // The count of sticks with the current // length has to be at least 4 // in order to form a square if (freq[i] >= 4) { cout << "Area = " << ( pow (i, 2)); cout << "\nCount = " << (freq[i] / 4); return ; } } // Impossible to form a square cout << "-1" ; } // Driver code int main() { int arr[] = { 2, 2, 2, 9, 2, 2, 2, 2, 2 }; int n = sizeof (arr) / sizeof (arr[0]); findMaxSquare(arr, n); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to find the area of the largest // square that can be formed // and the count of such squares static void findMaxSquare( int arr[], int n) { // Maximum value from the array int maxVal = Arrays.stream(arr).max().getAsInt(); // Update the frequencies of // the array elements int []freq = new int [maxVal + 1 ]; for ( int i = 0 ; i < n; i++) freq[arr[i]]++; // Starting from the maximum length sticks // in order to maximize the area for ( int i = maxVal; i > 0 ; i--) { // The count of sticks with the current // length has to be at least 4 // in order to form a square if (freq[i] >= 4 ) { System.out.print( "Area = " + (Math.pow(i, 2 ))); System.out.print( "\nCount = " + (freq[i] / 4 )); return ; } } // Impossible to form a square System.out.print( "-1" ); } // Driver code public static void main(String[] args) { int arr[] = { 2 , 2 , 2 , 9 , 2 , 2 , 2 , 2 , 2 }; int n = arr.length; findMaxSquare(arr, n); } } // This code is contributed by Princi Singh |
Python3
# Python3 implementation of the approach # Function to find the area of the largest # square that can be formed # and the count of such squares def findMaxSquare(arr, n) : # Maximum value from the array maxVal = max (arr); # Update the frequencies of # the array elements freq = [ 0 ] * (maxVal + 1 ) ; for i in range (n) : freq[arr[i]] + = 1 ; # Starting from the maximum length sticks # in order to maximize the area for i in range (maxVal, 0 , - 1 ) : # The count of sticks with the current # length has to be at least 4 # in order to form a square if (freq[i] > = 4 ) : print ( "Area = " , pow (i, 2 )); print ( "Count =" , freq[i] / / 4 ); return ; # Impossible to form a square print ( "-1" ); # Driver code if __name__ = = "__main__" : arr = [ 2 , 2 , 2 , 9 , 2 , 2 , 2 , 2 , 2 ]; n = len (arr); findMaxSquare(arr, n); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; using System.Linq; class GFG { // Function to find the area of the largest // square that can be formed // and the count of such squares static void findMaxSquare( int []arr, int n) { // Maximum value from the array int maxVal = arr.Max(); // Update the frequencies of // the array elements int []freq = new int [maxVal + 1]; for ( int i = 0; i < n; i++) freq[arr[i]]++; // Starting from the maximum length sticks // in order to maximize the area for ( int i = maxVal; i > 0; i--) { // The count of sticks with the current // length has to be at least 4 // in order to form a square if (freq[i] >= 4) { Console.Write( "Area = " + (Math.Pow(i, 2))); Console.Write( "\nCount = " + (freq[i] / 4)); return ; } } // Impossible to form a square Console.Write( "-1" ); } // Driver code public static void Main(String[] args) { int []arr = { 2, 2, 2, 9, 2, 2, 2, 2, 2 }; int n = arr.Length; findMaxSquare(arr, n); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach // Function to find the area of the largest // square that can be formed // and the count of such squares function findMaxSquare(arr, n) { // Maximum value from the array var maxVal = Math.max(...arr); // Update the frequencies of // the array elements var freq = Array(maxVal + 1).fill(0); for ( var i = 0; i < n; i++) freq[arr[i]]++; // Starting from the maximum length sticks // in order to maximize the area for ( var i = maxVal; i > 0; i--) { // The count of sticks with the current // length has to be at least 4 // in order to form a square if (freq[i] >= 4) { document.write( "Area = " + (Math.pow(i, 2))); document.write( "<br>Count = " + (freq[i] / 4)); return ; } } // Impossible to form a square document.write( "-1" ); } // Driver code var arr = [ 2, 2, 2, 9, 2, 2, 2, 2, 2 ]; var n = arr.length; findMaxSquare(arr, n); </script> |
Area = 4 Count = 2
Time Complexity: O(n)
Auxiliary Space: O(n)
Contact Us