Spočítejte páry, jejichž produkty existují v poli
Dané pole spočítejte ty páry, jejichž hodnota součinu je přítomna v poli.
Příklady:
Input : arr[] = {6 2 4 12 5 3}
Output : 3
All pairs whose product exist in array
(6 2) (2 3) (4 3)
Input : arr[] = {3 5 2 4 15 8}
Output : 2
C++
A Jednoduché řešení je vygenerovat všechny páry daného pole a zkontrolovat, zda produkt v poli existuje. Pokud existuje, zvýší se počet. Nakonec návratový počet.
Níže je implementace výše uvedené myšlenky
Java// C++ program to count pairs whose product exist in array #includeusing namespace std ; // Returns count of pairs whose product exists in arr[] int countPairs ( int arr [] int n ) { int result = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { int product = arr [ i ] * arr [ j ] ; // find product in an array for ( int k = 0 ; k < n ; k ++ ) { // if product found increment counter if ( arr [ k ] == product ) { result ++ ; break ; } } } } // return Count of all pair whose product exist in array return result ; } //Driver program int main () { int arr [] = { 6 2 4 12 5 3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < countPairs ( arr n ); return 0 ; } Python 3// Java program to count pairs // whose product exist in array import java.io.* ; class GFG { // Returns count of pairs // whose product exists in arr[] static int countPairs ( int arr [] int n ) { int result = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { int product = arr [ i ] * arr [ j ] ; // find product // in an array for ( int k = 0 ; k < n ; k ++ ) { // if product found // increment counter if ( arr [ k ] == product ) { result ++ ; break ; } } } } // return Count of all pair // whose product exist in array return result ; } // Driver Code public static void main ( String [] args ) { int arr [] = { 6 2 4 12 5 3 } ; int n = arr . length ; System . out . println ( countPairs ( arr n )); } } // This code is contributed by anuj_67.C## Python program to count pairs whose # product exist in array # Returns count of pairs whose # product exists in arr[] def countPairs ( arr n ): result = 0 ; for i in range ( 0 n ): for j in range ( i + 1 n ): product = arr [ i ] * arr [ j ] ; # find product in an array for k in range ( 0 n ): # if product found increment counter if ( arr [ k ] == product ): result = result + 1 ; break ; # return Count of all pair whose # product exist in array return result ; # Driver program arr = [ 6 2 4 12 5 3 ] ; n = len ( arr ); print ( countPairs ( arr n )); # This code is contributed # by Shivi_AggarwalJavaScript// C# program to count pairs // whose product exist in array using System ; class GFG { // Returns count of pairs // whose product exists in arr[] public static int countPairs ( int [] arr int n ) { int result = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { int product = arr [ i ] * arr [ j ]; // find product in an array for ( int k = 0 ; k < n ; k ++ ) { // if product found // increment counter if ( arr [ k ] == product ) { result ++ ; break ; } } } } // return Count of all pair // whose product exist in array return result ; } // Driver Code public static void Main ( string [] args ) { int [] arr = new int [] { 6 2 4 12 5 3 }; int n = arr . Length ; Console . WriteLine ( countPairs ( arr n )); } } // This code is contributed by Shrikant13PHP< script > // javascript program to count pairs // whose product exist in array // Returns count of pairs // whose product exists in arr function countPairs ( arr n ) { var result = 0 ; for ( i = 0 ; i < n ; i ++ ) { for ( j = i + 1 ; j < n ; j ++ ) { var product = arr [ i ] * arr [ j ]; // find product // in an array for ( k = 0 ; k < n ; k ++ ) { // if product found // increment counter if ( arr [ k ] == product ) { result ++ ; break ; } } } } // return Count of all pair // whose product exist in array return result ; } // Driver Code var arr = [ 6 2 4 12 5 3 ]; var n = arr . length ; document . write ( countPairs ( arr n )); // This code is contributed by Rajput-Ji < /script>výstup:
3
Časová složitost: Na 3 )Pomocný prostor: O(1)
C++
An Efektivní řešení je použít 'hash', který ukládá všechny prvky pole. Vygenerujte všechny možné dvojice daného pole 'arr' a zkontrolujte, zda je součin každého páru v 'hash'. Pokud existuje, zvýší se počet. Nakonec návratový počet.
Níže je implementace výše uvedené myšlenky
Java// A hashing based C++ program to count pairs whose product // exists in arr[] #includeusing namespace std ; // Returns count of pairs whose product exists in arr[] int countPairs ( int arr [] int n ) { int result = 0 ; // Create an empty hash-set that store all array element set < int > Hash ; // Insert all array element into set for ( int i = 0 ; i < n ; i ++ ) Hash . insert ( arr [ i ]); // Generate all pairs and check is exist in 'Hash' or not for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { int product = arr [ i ] * arr [ j ]; // if product exists in set then we increment // count by 1 if ( Hash . find ( product ) != Hash . end ()) result ++ ; } } // return count of pairs whose product exist in array return result ; } // Driver program int main () { int arr [] = { 6 2 4 12 5 3 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); cout < < countPairs ( arr n ) ; return 0 ; } Python3// A hashing based Java program to count pairs whose product // exists in arr[] import java.util.* ; class GFG { // Returns count of pairs whose product exists in arr[] static int countPairs ( int arr [] int n ) { int result = 0 ; // Create an empty hash-set that store all array element HashSet < Integer > Hash = new HashSet <> (); // Insert all array element into set for ( int i = 0 ; i < n ; i ++ ) { Hash . add ( arr [ i ] ); } // Generate all pairs and check is exist in 'Hash' or not for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { int product = arr [ i ] * arr [ j ] ; // if product exists in set then we increment // count by 1 if ( Hash . contains ( product )) { result ++ ; } } } // return count of pairs whose product exist in array return result ; } // Driver program public static void main ( String [] args ) { int arr [] = { 6 2 4 12 5 3 }; int n = arr . length ; System . out . println ( countPairs ( arr n )); } } // This code has been contributed by 29AjayKumarC## A hashing based C++ program to count # pairs whose product exists in arr[] # Returns count of pairs whose product # exists in arr[] def countPairs ( arr n ): result = 0 # Create an empty hash-set that # store all array element Hash = set () # Insert all array element into set for i in range ( n ): Hash . add ( arr [ i ]) # Generate all pairs and check is # exist in 'Hash' or not for i in range ( n ): for j in range ( i + 1 n ): product = arr [ i ] * arr [ j ] # if product exists in set then # we increment count by 1 if product in ( Hash ): result += 1 # return count of pairs whose # product exist in array return result # Driver Code if __name__ == '__main__' : arr = [ 6 2 4 12 5 3 ] n = len ( arr ) print ( countPairs ( arr n )) # This code is contributed by # Sanjit_PrasadJavaScript// A hashing based C# program to count pairs whose product // exists in arr[] using System ; using System.Collections.Generic ; class GFG { // Returns count of pairs whose product exists in arr[] static int countPairs ( int [] arr int n ) { int result = 0 ; // Create an empty hash-set that store all array element HashSet < int > Hash = new HashSet < int > (); // Insert all array element into set for ( int i = 0 ; i < n ; i ++ ) { Hash . Add ( arr [ i ]); } // Generate all pairs and check is exist in 'Hash' or not for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { int product = arr [ i ] * arr [ j ]; // if product exists in set then we increment // count by 1 if ( Hash . Contains ( product )) { result ++ ; } } } // return count of pairs whose product exist in array return result ; } // Driver code public static void Main ( String [] args ) { int [] arr = { 6 2 4 12 5 3 }; int n = arr . Length ; Console . WriteLine ( countPairs ( arr n )); } } /* This code contributed by PrinciRaj1992 */výstup:
3
Časová složitost: Na 2 ) 'Za předpokladu operace vložení hledání trvat O(1) Time 'Pomocný prostor: Na)
Metoda 3: Použití neuspořádané mapy
Přístup:
1. Vytvořte prázdnou mapu pro uložení prvků pole a jejich frekvencí.
2. Projděte pole a vložte každý prvek do mapy spolu s jeho frekvencí.
3. Inicializujte proměnnou počtu na 0, abyste měli přehled o počtu párů.
4. Znovu projděte pole a pro každý prvek zkontrolujte, zda má nějaký faktor (jiný než on sám), který je přítomen v mapě.
5.Pokud jsou v mapě přítomny oba faktory, zvyšte počet dvojic.
6.Vraťte počet párů.Implementace:
C++Java#includeusing namespace std ; // Function to count pairs whose product value is present in array int count_Pairs ( int arr [] int n ) { map < int int > mp ; // Create a map to store the elements of the array and their frequencies // Initialize the map with the frequencies of the elements in the array for ( int i = 0 ; i < n ; i ++ ) { mp [ arr [ i ]] ++ ; } int count = 0 ; // Initialize the count of pairs to zero // Traverse the array and check if arr[i] has a factor in the map for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 1 ; j * j <= arr [ i ]; j ++ ) { if ( arr [ i ] % j == 0 ) { int factor1 = j ; int factor2 = arr [ i ] / j ; // If both factors are present in the map then increment the count of pairs if ( mp . count ( factor1 ) && mp . count ( factor2 )) { if ( factor1 == factor2 && mp [ factor1 ] < 2 ) { continue ; } count ++ ; } } } } // Return the count of pairs return count ; } // Driver code int main () { // Example input int arr [] = { 6 2 4 12 5 3 }; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); // Count pairs whose product value is present in array int count = count_Pairs ( arr n ); // Print the count cout < < count < < endl ; return 0 ; } Pythonimport java.util.HashMap ; import java.util.Map ; public class Main { // Function to count pairs whose product value is // present in the array static int countPairs ( int [] arr ) { Map < Integer Integer > frequencyMap = new HashMap <> (); // Initialize the map with the frequencies of the // elements in the array for ( int num : arr ) { frequencyMap . put ( num frequencyMap . getOrDefault ( num 0 ) + 1 ); } int count = 0 ; // Initialize the count of pairs to zero // Traverse the array and check if arr[i] has a // factor in the map for ( int num : arr ) { for ( int j = 1 ; j * j <= num ; j ++ ) { if ( num % j == 0 ) { int factor1 = j ; int factor2 = num / j ; // If both factors are present in the // map then increment the count of // pairs if ( frequencyMap . containsKey ( factor1 ) && frequencyMap . containsKey ( factor2 )) { if ( factor1 == factor2 && frequencyMap . get ( factor1 ) < 2 ) { continue ; } count ++ ; } } } } // Return the count of pairs return count ; } public static void main ( String [] args ) { // Example input int [] arr = { 6 2 4 12 5 3 }; // Count pairs whose product value is present in the // array int count = countPairs ( arr ); // Print the count System . out . println ( count ); } }C## Function to count pairs whose product value is present in the array def count_pairs ( arr ): # Create a dictionary to store the elements of the array and their frequencies mp = {} # Initialize the dictionary with the frequencies of the elements in the array for num in arr : if num in mp : mp [ num ] += 1 else : mp [ num ] = 1 count = 0 # Initialize the count of pairs to zero # Traverse the array and check if arr[i] has a factor in the dictionary for num in arr : for j in range ( 1 int ( num ** 0.5 ) + 1 ): if num % j == 0 : factor1 = j factor2 = num // j # If both factors are present in the dictionary # then increment the count of pairs if factor1 in mp and factor2 in mp : if factor1 == factor2 and mp [ factor1 ] < 2 : continue count += 1 return count # Driver code if __name__ == '__main__' : # Example input arr = [ 6 2 4 12 5 3 ] # Count pairs whose product value is present in the array count = count_pairs ( arr ) # Print the count print ( count )JavaScriptusing System ; using System.Collections.Generic ; class GFG { // Function to count pairs whose product value is // present in array static int CountPairs ( int [] arr int n ) { Dictionary < int int > mp = new Dictionary < int int > (); // Create a dictionary to store the // elements of the array and their // frequencies // Initialize the dictionary with the frequencies of // the elements in the array for ( int i = 0 ; i < n ; i ++ ) { if ( ! mp . ContainsKey ( arr [ i ])) mp [ arr [ i ]] = 1 ; else mp [ arr [ i ]] ++ ; } int count = 0 ; // Initialize the count of pairs to zero // Traverse the array and check if arr[i] has a // factor in the dictionary for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 1 ; j * j <= arr [ i ]; j ++ ) { if ( arr [ i ] % j == 0 ) { int factor1 = j ; int factor2 = arr [ i ] / j ; // If both factors are present in the // dictionary then increment the count // of pairs if ( mp . ContainsKey ( factor1 ) && mp . ContainsKey ( factor2 )) { if ( factor1 == factor2 && mp [ factor1 ] < 2 ) { continue ; } count ++ ; } } } } // Return the count of pairs return count ; } // Driver code static void Main ( string [] args ) { // Example input int [] arr = { 6 2 4 12 5 3 }; int n = arr . Length ; // Count pairs whose product value is present in // array int count = CountPairs ( arr n ); // Print the count Console . WriteLine ( count ); } }výstup:
3
Časová složitost: O(n log n)
Pomocný prostor: Na)
Vytvořit kvíz
