Dada una array 2D A[][2] de tamaño N (1 ≤ N ≤ 10 3 ) , donde A[i][0] y A[i][1] denotan el largo y el ancho del rectángulo i respectivamente.
Dos rectángulos i y j donde (i < j) son similares si la razón de su largo y ancho es igual
A[i][0] / A[i][1] = A[j][0] / A[j][1]
La tarea es contar el par de rectángulos que son casi similares.
Ejemplos:
Entrada : A[][2] = {{4, 8}, {15, 30}, {3, 6}, {10, 20}}
Salida: 6
Explicación: Los pares de rectángulos similares son (0, 1), {0, 2), (0, 3), (1, 2), (1, 3), (2, 3). Para cada rectángulo, la relación de largo: ancho es 1: 2Entrada : A[][2] = {{2, 3}, {4, 5}, {7, 8}}
Salida: 0
Explicación: No existe ningún par de rectángulos similares.
Método 1 (método de comparación simple)
Enfoque: Siga los pasos para resolver el problema
- Atraviesa la array .
- Para cada par tal que ( i < j ), verifique si los rectángulos son similares o no verificando si la condición A[i][0] / A[i][1] = A[j][0] / A[ j][1] se cumple o no.
- Si se encuentra que es cierto, incremente el conteo.
- Finalmente, imprima el conteo obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program for the above approach #include <iostream> using namespace std; // Function to calculate the count // of similar rectangles int getCount(int rows, int columns, int A[][2]) { int res = 0; for (int i = 0; i < rows; i++) { for (int j = i + 1; j < rows; j++) { if (A[i][0] * 1LL * A[j][1] == A[i][1] * 1LL * A[j][0]) { res++; } } } return res; } // Driver Code int main() { // Input int A[][2] = { { 4, 8 }, { 10, 20 }, { 15, 30 }, { 3, 6 } }; int columns = 2; int rows = sizeof(A) / sizeof(A[0]); cout << getCount(rows, columns, A); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to calculate the count // of similar rectangles static int getCount(int rows, int columns, int[][] A) { int res = 0; for(int i = 0; i < rows; i++) { for(int j = i + 1; j < rows; j++) { if (A[i][0] * A[j][1] == A[i][1] * A[j][0]) { res++; } } } return res; } // Driver Code public static void main(String[] args) { // Input int[][] A = { { 4, 8 }, { 10, 20 }, { 15, 30 }, { 3, 6 } }; int columns = 2; int rows = 4; System.out.print(getCount(rows, columns, A)); } } // This code is contributed by code_hunt.
Python3
# Python3 program for the above approach # Function to calculate the count # of similar rectangles def getCount(rows, columns, A): res = 0 for i in range(rows): for j in range(i + 1, rows, 1): if (A[i][0] * A[j][1] == A[i][1] * A[j][0]): res += 1 return res # Driver Code if __name__ == '__main__': # Input A = [ [ 4, 8 ], [ 10, 20 ], [ 15, 30 ], [ 3, 6 ] ] columns = 2 rows = len(A) print(getCount(rows, columns, A)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach using System; class GFG{ // Function to calculate the count // of similar rectangles static int getCount(int rows, int columns, int[,] A) { int res = 0; for(int i = 0; i < rows; i++) { for(int j = i + 1; j < rows; j++) { if (A[i, 0] * A[j, 1] == A[i, 1] * A[j, 0]) { res++; } } } return res; } // Driver code static void Main() { // Input int[,] A = { { 4, 8 }, { 10, 20 }, { 15, 30 }, { 3, 6 } }; int columns = 2; int rows = 4; Console.Write(getCount(rows, columns, A)); } } // This code is contributed by divyesh072019
Javascript
<script> // Javascript program for the above approach // Function to calculate the count // of similar rectangles function getCount(rows, columns, A) { var res = 0; for(var i = 0; i < rows; i++) { for(var j = i + 1; j < rows; j++) { if (A[i][0] * A[j][1] == A[i][1] * A[j][0]) { res++; } } } return res; } // Driver Code // Input var A = [ [ 4, 8 ], [ 10, 20 ], [ 15, 30 ], [ 3, 6 ] ]; var columns = 2; var rows = 4; document.write(getCount(rows, columns, A)); // This code is contributed by kirti </script>
6
Complejidad de Tiempo : O(N 2 )
Espacio Auxiliar : O(1)
Método 2 (usando HashMap)
En lugar de comparar directamente la proporción de un rectángulo con la de otro rectángulo, podemos almacenar todas las proporciones calculadas en el HashMap. Dado que HashMap tiene el costo de acceso de O (1), eso permitiría una búsqueda rápida de otros rectángulos con la misma proporción y almacenarlos juntos. El número de pares de rectángulos similares se puede derivar del número de rectángulos con la misma razón usando \frac{N \times (N – 1)}{2}. La razón por la que uno puede usar la ecuación mencionada para encontrar el número de pares de rectángulos similares es que el número de pares aumenta cada vez que se agrega un rectángulo con la misma proporción.
C++
// C++ Program for the hashmap Approach #include <iostream> #include <unordered_map> using namespace std; // Get the count of all pairs of similar rectangles int getCount(int rows, int columns, int sides[][2]) { // Initialize the result value and // map to store the ratio to the rectangles int ans = 0; unordered_map<double, int> umap; // Calculate the rectangular ratio and save them for (int i = 0; i < rows; i++) { double ratio = (double)sides[i][0] / sides[i][1]; umap[ratio]++; } // Calculate pairs of similar rectangles from its common ratio for (auto x : umap) { int value = x.second; if (value > 1) { ans += (value * (value - 1)) / 2; } } return ans; } int main() { int sides[4][2] = {{4, 8}, {10, 20}, {15, 30}, {3, 6}}; int rows = 4; int columns = 2; cout << getCount(rows, columns, sides); return 0; //this code is contributed by krishna_6431 }
Java
import java.util.*; class GFG { // Get the count of all pairs of similar rectangles public static int getCount(int rows, int columns, int[][] sides) { // Initialize the result value and // map to store the ratio to the rectangles int res = 0; Map<Double, Integer> ratio = new HashMap<Double, Integer>(); // Calculate the rectangular ratio and save them for (int i = 0; i < rows; i++) { double rectRatio = (double) sides[i][0] / sides[i][1]; if (ratio.get(rectRatio) == null) { ratio.put(rectRatio, 0); } ratio.put(rectRatio, ratio.get(rectRatio) + 1); } // Calculate pairs of similar rectangles from // its common ratio for (double key : ratio.keySet()) { int val = ratio.get(key); if (val > 1) { res += (val * (val - 1)) / 2; } } return res; } public static void main(String[] args) { int[][] A = {{4, 8}, {10, 20}, {15, 30}, {3, 6}}; int columns = 2; int rows = 4; System.out.println(getCount(rows, columns, A)); } } // This code is contributed by nathnet
Python3
# Python 3 Program for the hashmap Approach from collections import defaultdict # Get the count of all pairs of similar rectangles def getCount(rows, columns, sides): # Initialize the result value and # map to store the ratio to the rectangles ans = 0 umap = defaultdict(int) # Calculate the rectangular ratio and save them for i in range(rows): ratio = sides[i][0] / sides[i][1] umap[ratio] += 1 # Calculate pairs of similar rectangles from its common ratio for x in umap: value = umap[x] if (value > 1): ans += (value * (value - 1)) / 2 return ans # Driver code if __name__ == "__main__": sides = [[4, 8], [10, 20], [15, 30], [3, 6]] rows = 4 columns = 2 print(int(getCount(rows, columns, sides))) # This code is contributed by ukasp.
C#
using System; using System.Collections.Generic; class GFG { // Get the count of all pairs of similar rectangles public static int getCount(int rows, int columns, int[, ] sides) { // Initialize the result value and // map to store the ratio to the rectangles int res = 0; Dictionary<double, int> ratio = new Dictionary<double, int>(); // Calculate the rectangular ratio and save them for (int i = 0; i < rows; i++) { double rectRatio = (double)sides[i, 0] / sides[i, 1]; if (!ratio.ContainsKey(rectRatio)) { ratio[rectRatio] = 0; } ratio[rectRatio] = ratio[rectRatio] + 1; } // Calculate pairs of similar rectangles from // its common ratio foreach(KeyValuePair<double, int> p in ratio) { int val = p.Value; if (val > 1) { res += (val * (val - 1)) / 2; } } return res; } // Driver code public static void Main(string[] args) { int[, ] A = { { 4, 8 }, { 10, 20 }, { 15, 30 }, { 3, 6 } }; int columns = 2; int rows = 4; Console.WriteLine(getCount(rows, columns, A)); } } // This code is contributed by ukasp.
Javascript
<script> // JavaScript Program for the hashmap Approach // Get the count of all pairs of similar rectangles function getCount(rows, columns, sides) { // Initialize the result value and // map to store the ratio to the rectangles let ans = 0; let umap = new Map(); // Calculate the rectangular ratio and save them for (let i = 0; i < rows; i++) { let ratio = sides[i][0] / sides[i][1]; if(umap.has(ratio)){ umap.set(ratio,umap.get(ratio)+1); } else umap.set(ratio,1); } // Calculate pairs of similar rectangles from its common ratio for (let [x,y] of umap) { let value = y; if (value > 1) { ans += (value * (value - 1)) / 2; } } return ans; } // driver code let sides = [[4, 8], [10, 20], [15, 30], [3, 6]]; let rows = 4; let columns = 2; document.write(getCount(rows, columns, sides)); // This code is contributed by shinjanpatra </script>
6
Complejidad de tiempo : O(N)
Espacio Auxiliar : O(N)
Publicación traducida automáticamente
Artículo escrito por udaykiran9810 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA