Dado ‘N’ número de palos de longitud a 1 , a 2 , a 3 … a n . La tarea es contar el número de cuadrados y rectángulos posibles.
Nota: Un palo debe usarse solo una vez, es decir, en cualquiera de los cuadrados o rectángulos.
Ejemplos:
Input: arr[] = {1, 2, 1, 2}
Output: 1
Rectangle with sides 1 1 2 2
Input: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}
Output: 0
No square or rectangle is possible
Enfoque: a continuación se muestra el algoritmo paso a paso para resolver este problema:
- Inicialice el número de palos.
- Inicialice todos los palos con sus longitudes en una array.
- Ordena la array en orden creciente.
- Calcula el número de pares de palos con la misma longitud.
- Divide el número total de pares entre 2, que será el total de rectángulo y cuadrado posibles.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the possible
// rectangles and squares
int rectangleSquare(int arr[], int n)
{
// sort all the sticks
sort(arr, arr + n);
int count = 0;
// calculate all the pair of
// sticks with same length
for (int i = 0; i < n - 1; i++) {
if (arr[i] == arr[i + 1]) {
count++;
i++;
}
}
// divide the total number of pair
// which will be the number of possible
// rectangle and square
return count / 2;
}
// Driver code
int main()
{
// initialize all the stick lengths
int arr[] = { 2, 2, 4, 4, 4, 4, 6, 6, 6, 7, 7, 9, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << rectangleSquare(arr, n);
return 0;
}
Java
// Java implementation of above approach
import java.util.Arrays;
class GFG
{
// Function to find the possible
// rectangles and squares
static int rectangleSquare(int arr[], int n)
{
// sort all the sticks
Arrays.sort(arr);
int count = 0;
// calculate all the pair of
// sticks with same length
for (int i = 0; i < n - 1; i++)
{
if (arr[i] == arr[i + 1])
{
count++;
i++;
}
}
// divide the total number of pair
// which will be the number of possible
// rectangle and square
return count / 2;
}
// Driver code
public static void main(String[] args)
{
// initialize all the stick lengths
int arr[] = {2, 2, 4, 4, 4, 4, 6, 6, 6, 7, 7, 9, 9};
int n = arr.length;
System.out.println(rectangleSquare(arr, n));
}
}
// This code is contributed
// by PrinciRaj1992
Python3
# Python3 implementation of above approach
# Function to find the possible
# rectangles and squares
def rectangleSquare( arr, n):
# sort all the sticks
arr.sort()
count = 0
#print(" xx",arr[6])
# calculate all the pair of
# sticks with same length
k=0
for i in range(n-1):
if(k==1):
k=0
continue
if (arr[i] == arr[i + 1]):
count=count+1
k=1
# divide the total number of pair
# which will be the number of possible
# rectangle and square
return count/2
# Driver code
if __name__=='__main__':
# initialize all the stick lengths
arr = [2, 2, 4, 4, 4, 4, 6, 6, 6, 7, 7, 9, 9]
n = len(arr)
print(rectangleSquare(arr, n))
# this code is written by ash264
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to find the possible
// rectangles and squares
static int rectangleSquare(int []arr, int n)
{
// sort all the sticks
Array.Sort(arr);
int count = 0;
// calculate all the pair of
// sticks with same length
for (int i = 0; i < n - 1; i++)
{
if (arr[i] == arr[i + 1])
{
count++;
i++;
}
}
// divide the total number of pair
// which will be the number of possible
// rectangle and square
return count / 2;
}
// Driver code
public static void Main(String[] args)
{
// initialize all the stick lengths
int []arr = {2, 2, 4, 4, 4, 4, 6,
6, 6, 7, 7, 9, 9};
int n = arr.Length;
Console.WriteLine(rectangleSquare(arr, n));
}
}
// This code has been contributed
// by Rajput-Ji
PHP
<?php
// PHP implementation of above approach
// Function to find the possible
// rectangles and squares
function rectangleSquare($arr, $n)
{
// sort all the sticks
sort($arr);
$count = 0;
// calculate all the pair of
// sticks with same length
for ($i = 0; $i < $n - 1; $i++)
{
if ($arr[$i] == $arr[$i + 1])
{
$count++;
$i++;
}
}
// divide the total number of pair
// which will be the number of possible
// rectangle and square
return ($count / 2);
}
// Driver code
// initialize all the stick lengths
$arr = array(2, 2, 4, 4, 4, 4, 6,
6, 6, 7, 7, 9, 9 );
$n = sizeof($arr);
echo rectangleSquare($arr, $n);
// This code is contributed by Sachin.
?>
Javascript
<script>
// javascript implementation of above approach
// Function to find the possible
// rectangles and squares
function rectangleSquare(arr , n)
{
// sort all the sticks
arr.sort();
var count = 0;
// calculate all the pair of
// sticks with same length
for (i = 0; i < n - 1; i++)
{
if (arr[i] == arr[i + 1])
{
count++;
i++;
}
}
// divide the total number of pair
// which will be the number of possible
// rectangle and square
return count / 2;
}
// Driver code
// initialize all the stick lengths
var arr = [2, 2, 4, 4, 4, 4, 6, 6, 6, 7, 7, 9, 9];
var n = arr.length;
document.write(rectangleSquare(arr, n));
// This code is contributed by 29AjayKumar
</script>
Producción:
3
Complejidad de tiempo: O(n*log n) donde n es el tamaño de la array.
Espacio Auxiliar: O(1)