Dada una array arr[] de tamaño N , la tarea es contar el número de pares de la array dada cuyo producto contiene solo un único factor primo distinto.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: 4
Explicación:
Los pares que tienen un solo factor primo distinto en su producto son los siguientes:
arr[0] * arr[1] = (1 * 2) = 2 Por lo tanto, el único factor primo distinto es 2.
arr[0] * arr[2] = (1 * 3) = 3. Por lo tanto, el único factor primo distinto es 3.
arr[0] * arr[3] = ( 1 * 4) = 2 2 Por lo tanto, el único factor primo distinto es 2.
arr[1] * arr[3] = (2 * 4) = 8 2 3 Por lo tanto, el único factor primo distinto es 2.
Por lo tanto, el la salida es 4Entrada: arr[] = {2, 4, 6, 8}
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y generar todos los pares posibles de la array y, para cada par, verificar si el producto de los elementos contiene solo un factor primo distinto o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo.
Complejidad temporal: O(N 2 * √X), donde X es el producto máximo posible de un par en el arreglo dado.
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar Hashing . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos cntof1 para almacenar el recuento de elementos de array cuyo valor es 1 .
- Cree un mapa , digamos mp para almacenar el recuento de elementos de array que contiene solo un factor primo distinto .
- Recorra la array y, para cada elemento de la array, verifique si el recuento de factores primos distintos es 1 o no. Si se determina que es cierto, inserte el elemento actual en mp .
- Inicialice una variable, digamos res , para almacenar el recuento de pares cuyo producto de elementos contiene solo un único factor primo distinto.
- Recorra el mapa y actualice la res += cntof1 * (X) + (X *(X- 1)) / 2 . Donde X almacena el conteo del elemento de array que contiene solo un único factor primo distinto i .
- Finalmente, imprima el valor de res .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find a single // distinct prime factor of N int singlePrimeFactor(int N) { // Stores distinct // prime factors of N unordered_set<int> disPrimeFact; // Calculate prime factor of N for (int i = 2; i * i <= N; ++i) { // Calculate distinct // prime factor while (N % i == 0) { // Insert i into // disPrimeFact disPrimeFact.insert(i); // Update N N /= i; } } // If N is not equal to 1 if (N != 1) { // Insert N into // disPrimeFact disPrimeFact.insert(N); } // If N contains a single // distinct prime factor if (disPrimeFact.size() == 1) { // Return single distinct // prime factor of N return *disPrimeFact.begin(); } // If N contains more than one // distinct prime factor return -1; } // Function to count pairs in the array // whose product contains only // single distinct prime factor int cntsingleFactorPair(int arr[], int N) { // Stores count of 1s // in the array int countOf1 = 0; // mp[i]: Stores count of array elements // whose distinct prime factor is only i unordered_map<int, int> mp; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If current element is 1 if(arr[i] == 1) { countOf1++; continue; } // Store distinct // prime factor of arr[i] int factorValue = singlePrimeFactor(arr[i]); // If arr[i] contains more // than one prime factor if (factorValue == -1) { continue; } // If arr[i] contains // a single prime factor else { mp[factorValue]++; } } // Stores the count of pairs whose // product of elements contains only // a single distinct prime factor int res = 0; // Traverse the map mp[] for (auto it : mp) { // Stores count of array elements // whose prime factor is (it.first) int X = it.second; // Update res res += countOf1 * X + (X * (X - 1) ) / 2; } return res; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4 }; int N = sizeof(arr) / sizeof(arr[0]); cout << cntsingleFactorPair(arr, N); return 0; }
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to find a single // distinct prime factor of N static int singlePrimeFactor(int N) { // Stores distinct // prime factors of N HashSet<Integer> disPrimeFact = new HashSet<>(); // Calculate prime factor of N for (int i = 2; i * i <= N; ++i) { // Calculate distinct // prime factor while (N % i == 0) { // Insert i into // disPrimeFact disPrimeFact.add(i); // Update N N /= i; } } // If N is not equal to 1 if (N != 1) { // Insert N into // disPrimeFact disPrimeFact.add(N); } // If N contains a single // distinct prime factor if (disPrimeFact.size() == 1) { // Return single distinct // prime factor of N for(int i : disPrimeFact) return i; } // If N contains more than // one distinct prime factor return -1; } // Function to count pairs in // the array whose product // contains only single distinct // prime factor static int cntsingleFactorPair(int arr[], int N) { // Stores count of 1s // in the array int countOf1 = 0; // mp[i]: Stores count of array // elements whose distinct prime // factor is only i HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Traverse the array arr[] for (int i = 0; i < N; i++) { // If current element is 1 if(arr[i] == 1) { countOf1++; continue; } // Store distinct // prime factor of arr[i] int factorValue = singlePrimeFactor(arr[i]); // If arr[i] contains more // than one prime factor if (factorValue == -1) { continue; } // If arr[i] contains // a single prime factor else { if(mp.containsKey(factorValue)) mp.put(factorValue, mp.get(factorValue) + 1); else mp.put(factorValue, 1); } } // Stores the count of pairs whose // product of elements contains only // a single distinct prime factor int res = 0; // Traverse the map mp[] for (Map.Entry<Integer, Integer> it : mp.entrySet()) { // Stores count of array // elements whose prime // factor is (it.first) int X = it.getValue(); // Update res res += countOf1 * X + (X * (X - 1) ) / 2; } return res; } // Driver Code public static void main(String[] args) { int arr[] = {1, 2, 3, 4}; int N = arr.length; System.out.print( cntsingleFactorPair(arr, N)); } } // This code is contributed by gauravrajput1
Python3
# Python3 program to implement # the above approach # Function to find a single # distinct prime factor of N def singlePrimeFactor(N): # Stores distinct # prime factors of N disPrimeFact = {} # Calculate prime factor of N for i in range(2, N + 1): if i * i > N: break # Calculate distinct # prime factor while (N % i == 0): # Insert i into # disPrimeFact disPrimeFact[i] = 1 # Update N N //= i # If N is not equal to 1 if (N != 1): # Insert N into # disPrimeFact disPrimeFact[N] = 1 # If N contains a single # distinct prime factor if (len(disPrimeFact) == 1): # Return single distinct # prime factor of N return list(disPrimeFact.keys())[0] # If N contains more than one # distinct prime factor return -1 # Function to count pairs in the array # whose product contains only # single distinct prime factor def cntsingleFactorPair(arr, N): # Stores count of 1s # in the array countOf1 = 0 # mp[i]: Stores count of array elements # whose distinct prime factor is only i mp = {} # Traverse the array arr[] for i in range(N): # If current element is 1 if (arr[i] == 1): countOf1 += 1 continue # Store distinct # prime factor of arr[i] factorValue = singlePrimeFactor(arr[i]) # If arr[i] contains more # than one prime factor if (factorValue == -1): continue # If arr[i] contains # a single prime factor else: mp[factorValue] = mp.get(factorValue, 0) + 1 # Stores the count of pairs whose # product of elements contains only # a single distinct prime factor res = 0 # Traverse the map mp[] for it in mp: # Stores count of array elements # whose prime factor is (it.first) X = mp[it] # Update res res += countOf1 * X + (X * (X - 1) ) // 2 return res # Driver Code if __name__ == '__main__': arr = [ 1, 2, 3, 4 ] N = len(arr) print(cntsingleFactorPair(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to find a single // distinct prime factor of N static int singlePrimeFactor(int N) { // Stores distinct // prime factors of N HashSet<int> disPrimeFact = new HashSet<int>(); // Calculate prime factor of N for (int i = 2; i * i <= N; ++i) { // Calculate distinct // prime factor while (N % i == 0) { // Insert i into // disPrimeFact disPrimeFact.Add(i); // Update N N /= i; } } // If N is not equal to 1 if(N != 1) { // Insert N into // disPrimeFact disPrimeFact.Add(N); } // If N contains a single // distinct prime factor if (disPrimeFact.Count == 1) { // Return single distinct // prime factor of N foreach(int i in disPrimeFact) return i; } // If N contains more than // one distinct prime factor return -1; } // Function to count pairs in // the array whose product // contains only single distinct // prime factor static int cntsingleFactorPair(int []arr, int N) { // Stores count of 1s // in the array int countOf1 = 0; // mp[i]: Stores count of array // elements whose distinct prime // factor is only i Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array arr[] for (int i = 0; i < N; i++) { // If current element is 1 if(arr[i] == 1) { countOf1++; continue; } // Store distinct // prime factor of arr[i] int factorValue = singlePrimeFactor(arr[i]); // If arr[i] contains more // than one prime factor if (factorValue == -1) { continue; } // If arr[i] contains // a single prime factor else { if(mp.ContainsKey(factorValue)) mp[factorValue] = mp[factorValue] + 1; else mp.Add(factorValue, 1); } } // Stores the count of pairs whose // product of elements contains only // a single distinct prime factor int res = 0; // Traverse the map mp[] foreach(KeyValuePair<int, int> ele1 in mp) { // Stores count of array // elements whose prime // factor is (it.first) int X = ele1.Value; // Update res res += countOf1 * X + (X * (X - 1) ) / 2; } return res; } // Driver Code public static void Main() { int []arr = {1, 2, 3, 4}; int N = arr.Length; Console.WriteLine( cntsingleFactorPair(arr, N)); } } // This code is contributed by bgangwar59
Javascript
<script> // JavaScript program to implement // the above approach // Function to find a single // distinct prime factor of N function singlePrimeFactor(N) { // Stores distinct // prime factors of N var disPrimeFact = {}; // Calculate prime factor of N for(var i = 2; i * i <= N; ++i) { // Calculate distinct // prime factor while (N % i === 0) { // Insert i into // disPrimeFact disPrimeFact[i] = 1; // Update N N = parseInt(N / i); } } // If N is not equal to 1 if (N !== 1) { // Insert N into // disPrimeFact disPrimeFact[N] = 1; } // If N contains a single // distinct prime factor if (Object.keys(disPrimeFact).length === 1) { // Return single distinct // prime factor of N for(const [key, value] of Object.entries( disPrimeFact)) { return key; } } // If N contains more than // one distinct prime factor return -1; } // Function to count pairs in // the array whose product // contains only single distinct // prime factor function cntsingleFactorPair(arr, N) { // Stores count of 1s // in the array var countOf1 = 0; // mp[i]: Stores count of array // elements whose distinct prime // factor is only i var mp = {}; // Traverse the array arr[] for(var i = 0; i < N; i++) { // If current element is 1 if (arr[i] === 1) { countOf1++; continue; } // Store distinct // prime factor of arr[i] var factorValue = singlePrimeFactor(arr[i]); // If arr[i] contains more // than one prime factor if (factorValue === -1) { continue; } // If arr[i] contains // a single prime factor else { if (mp.hasOwnProperty(factorValue)) mp[factorValue] = mp[factorValue] + 1; else mp[factorValue] = 1; } } // Stores the count of pairs whose // product of elements contains only // a single distinct prime factor var res = 0; // Traverse the map mp[] for(const [key, value] of Object.entries(mp)) { // Stores count of array // elements whose prime // factor is (it.first) var X = value; // Update res res = parseInt(res + countOf1 * X + (X * (X - 1)) / 2); } return res; } // Driver Code var arr = [ 1, 2, 3, 4 ]; var N = arr.length; document.write(cntsingleFactorPair(arr, N)); // This code is contributed by rdtank </script>
4
Complejidad de tiempo: O(N√X) , donde X es el elemento máximo de la array dada.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por math_lover y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA