Dada una array arr[] de N enteros que representan las alturas de los palos. La tarea es encontrar el área del cuadrado más grande que se puede formar usando estos palos y la cantidad de cuadrados. Tenga en cuenta que un solo lado del cuadrado solo puede usar un solo palo.
Ejemplos:
Entrada: arr[] = {5, 3, 2, 3, 6, 3, 3}
Salida:
Área = 9
Cuenta = 1
El lado del cuadrado será 3 y
solo uno de esos cuadrados es posible.
Entrada: arr[] = {2, 2, 2, 9, 2, 2, 2, 2, 2}
Salida:
Área = 4
Conteo = 2
Enfoque: Cuente las frecuencias de todos los elementos de la array. Ahora, comenzando desde el máximo (para maximizar el área), encuentre la primera frecuencia que es al menos 4 para que se pueda formar un cuadrado, luego el área se puede calcular como freq[i] * freq[i] y la cuenta de dichos cuadrados serán freq[i] / 4.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
Area = 4 Count = 2
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por KunalGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA