Dada una array arr[] de N enteros donde arr[i] es la altura del i- ésimo chocolate y todos los chocolates tienen 1 unidad de ancho, la tarea es encontrar el área máxima para cualquier cuadrado hecho con los chocolates cuando los chocolates pueden organizarse en cualquier orden.
Ejemplos:
Entrada: arr[] = {1, 3, 4, 5, 5}
Salida: 9
Cuadrado con lado = 3 se puede obtener
de {3, 4, 5} o {4, 5, 5}.
Entrada: arr[] = {6, 1, 6, 6, 6}
Salida: 16
Enfoque: se puede obtener un cuadrado de lado a si existe al menos un elemento en la array que sea igual o mayor que a . La búsqueda binaria se puede utilizar para encontrar el lado máximo del cuadrado que se puede lograr dentro del rango de 0 a N.
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 that returns true if it
// is possible to make a square
// with side equal to l
bool isSquarePossible(int arr[], int n, int l)
{
// To store the count of elements
// greater than or equal to l
int cnt = 0;
for (int i = 0; i < n; i++) {
// Increment the count
if (arr[i] >= l)
cnt++;
// If the count becomes greater
// than or equal to l
if (cnt >= l)
return true;
}
return false;
}
// Function to return the
// maximum area of the square
// that can be obtained
int maxArea(int arr[], int n)
{
int l = 0, r = n;
int len = 0;
while (l <= r) {
int m = l + ((r - l) / 2);
// If square is possible with
// side length m
if (isSquarePossible(arr, n, m)) {
len = m;
l = m + 1;
}
// Try to find a square with
// smaller side length
else
r = m - 1;
}
// Return the area
return (len * len);
}
// Driver code
int main()
{
int arr[] = { 1, 3, 4, 5, 5 };
int n = sizeof(arr) / sizeof(int);
cout << maxArea(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function that returns true if it
// is possible to make a square
// with side equal to l
static boolean isSquarePossible(int arr[],
int n, int l)
{
// To store the count of elements
// greater than or equal to l
int cnt = 0;
for (int i = 0; i < n; i++)
{
// Increment the count
if (arr[i] >= l)
cnt++;
// If the count becomes greater
// than or equal to l
if (cnt >= l)
return true;
}
return false;
}
// Function to return the
// maximum area of the square
// that can be obtained
static int maxArea(int arr[], int n)
{
int l = 0, r = n;
int len = 0;
while (l <= r)
{
int m = l + ((r - l) / 2);
// If square is possible with
// side length m
if (isSquarePossible(arr, n, m))
{
len = m;
l = m + 1;
}
// Try to find a square with
// smaller side length
else
r = m - 1;
}
// Return the area
return (len * len);
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 3, 4, 5, 5 };
int n = arr.length;
System.out.println(maxArea(arr, n));
}
}
// This code is contributed by kanugargng
Python3
# Python3 implementation of the approach # Function that returns true if it # is possible to make a square # with side equal to l def isSquarePossible(arr, n, l) : # To store the count of elements # greater than or equal to l cnt = 0 for i in range(n) : # Increment the count if arr[i] >= l : cnt += 1 # If the count becomes greater # than or equal to l if cnt >= l : return True return False # Function to return the # maximum area of the square # that can be obtained def maxArea(arr, n) : l , r = 0, n len = 0 while l <= r : m = l + ((r - l) // 2) # If square is possible with # side length m if isSquarePossible(arr, n, m) : len = m l = m + 1 # Try to find a square with # smaller side length else : r = m - 1 # Return the area return (len * len) # Driver code arr = [ 1, 3, 4, 5, 5 ] n = len(arr) print(maxArea(arr, n)) # This code is contributed by divyamohan
C#
// C# implementation of the approach
using System;
class GFG
{
// Function that returns true if it
// is possible to make a square
// with side equal to l
static bool isSquarePossible(int []arr,
int n, int l)
{
// To store the count of elements
// greater than or equal to l
int cnt = 0;
for (int i = 0; i < n; i++)
{
// Increment the count
if (arr[i] >= l)
cnt++;
// If the count becomes greater
// than or equal to l
if (cnt >= l)
return true;
}
return false;
}
// Function to return the
// maximum area of the square
// that can be obtained
static int maxArea(int []arr, int n)
{
int l = 0, r = n;
int len = 0;
while (l <= r)
{
int m = l + ((r - l) / 2);
// If square is possible with
// side length m
if (isSquarePossible(arr, n, m))
{
len = m;
l = m + 1;
}
// Try to find a square with
// smaller side length
else
r = m - 1;
}
// Return the area
return (len * len);
}
// Driver code
public static void Main()
{
int []arr = { 1, 3, 4, 5, 5 };
int n = arr.Length;
Console.WriteLine(maxArea(arr, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// JavaScript implementation of the approach
// Function that returns true if it
// is possible to make a square
// with side equal to l
function isSquarePossible(arr, n, l) {
// To store the count of elements
// greater than or equal to l
let cnt = 0;
for (let i = 0; i < n; i++) {
// Increment the count
if (arr[i] >= l)
cnt++;
// If the count becomes greater
// than or equal to l
if (cnt >= l)
return true;
}
return false;
}
// Function to return the
// maximum area of the square
// that can be obtained
function maxArea(arr, n) {
let l = 0, r = n;
let len = 0;
while (l <= r) {
let m = l + Math.floor((r - l) / 2);
// If square is possible with
// side length m
if (isSquarePossible(arr, n, m)) {
len = m;
l = m + 1;
}
// Try to find a square with
// smaller side length
else
r = m - 1;
}
// Return the area
return (len * len);
}
// Driver code
let arr = [1, 3, 4, 5, 5];
let n = arr.length;
document.write(maxArea(arr, n));
</script>
Producción:
9
Complejidad de tiempo: O(n * log n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por divyamohan123 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA