Dada una array arr[] , la tarea es contar todos los pares cuyo xor da el primo único, es decir, no hay dos pares que den el mismo primo.
Ejemplos:
Entrada: arr[] = {2, 3, 4, 5, 6, 7, 8, 9}
Salida: 6
(2, 5), (2, 7), (2, 9), (4, 6), (4, 7) y (4, 9) son los únicos pares cuyos XOR son primos, es decir, 7, 5, 11, 2, 3 y 13 respectivamente.
Entrada: arr[] = {10, 12, 23, 45, 5, 6}
Salida: 4
Enfoque: iterar todos los pares posibles y verificar si el xor del par actual es un primo. Si es un número primo, actualice count = count + 1 y también guarde el número primo en un mapa_desordenado para realizar un seguimiento de los números primos que se repiten. Imprime el conteo al final.
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 that returns true if n is prime bool isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to return the count of valid pairs int countPairs(int a[], int n) { int count = 0; unordered_map<int, int> m; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // If xor(a[i], a[j]) is prime and unique if (isPrime(a[i] ^ a[j]) && m[a[i] ^ a[j]] == 0) { m[(a[i] ^ a[j])]++; count++; } } } return count; } // Driver code int main() { int a[] = { 10, 12, 23, 45, 5, 6 }; int n = sizeof(a) / sizeof(a[0]); cout << countPairs(a, n); }
Java
// Java implementation of above approach import java.util.*; class solution { // Function that returns true if n is prime static boolean isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to return the count of valid pairs static int countPairs(int a[], int n) { int count = 0; Map<Integer, Integer> m=new HashMap< Integer,Integer>(); for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // If xor(a[i], a[j]) is prime and unique if (isPrime(a[i] ^ a[j]) && m.get(a[i] ^ a[j]) == null) { m.put((a[i] ^ a[j]),1); count++; } } } return count; } // Driver code public static void main(String args[]) { int a[] = { 10, 12, 23, 45, 5, 6 }; int n = a.length; System.out.println(countPairs(a, n)); } } // This code is contributed by Arnab Kundu
Python3
# Python3 implementation of above approach # Function that returns true if n is prime def isPrime(n): # Corner cases if n <= 1: return False if n <= 3: return True # This is checked so that we can skip # middle five numbers in below loop if n % 2 == 0 or n % 3 == 0: return False i = 5 while i * i <= n: if n % i == 0 or n % (i + 2) == 0: return False i += 6 return True # Function to return the count of valid pairs def countPairs(a, n): count = 0 m = dict() for i in range(n - 1): for j in range(i + 1, n): # If xor(a[i], a[j]) is prime and unique if isPrime(a[i] ^ a[j]) and m.get(a[i] ^ a[j], 0) == 0: m[(a[i] ^ a[j])] = 1 count += 1 return count # Driver code a = [10, 12, 23, 45, 5, 6] n = len(a) print(countPairs(a, n)) # This code is contributed by # Rajnis09
C#
// C# implementation of the approach using System ; using System.Collections ; class solution { // Function that returns true if n is prime static bool isPrime(int n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to return the count of valid pairs static int countPairs(int []a, int n) { int count = 0; Hashtable m=new Hashtable(); for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { // If xor(a[i], a[j]) is prime and unique if (isPrime(a[i] ^ a[j]) && m[a[i] ^ a[j]] == null) { m.Add((a[i] ^ a[j]),1); count++; } } } return count; } // Driver code public static void Main() { int []a = { 10, 12, 23, 45, 5, 6 }; int n = a.Length; Console.WriteLine(countPairs(a, n)); } // This code is contributed by Ryuga }
Javascript
<script> // Javascript implementation of above approach // Function that returns true if n is prime function isPrime(n) { // Corner cases if (n <= 1) return false; if (n <= 3) return true; // This is checked so that we can skip // middle five numbers in below loop if (n % 2 == 0 || n % 3 == 0) return false; for (let i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } // Function to return the count of valid pairs function countPairs(a,n) { let count = 0; let m = new Map(); for (let i = 0; i < n - 1; i++) { for (let j = i + 1; j < n; j++) { // If xor(a[i], a[j]) is prime and unique if (isPrime(a[i] ^ a[j]) && !m.has(a[i] ^ a[j])) { m.set((a[i] ^ a[j]), 1); count++; } } } return count; } // Driver code let a = [10, 12, 23, 45, 5, 6]; let n = a.length; document.write(countPairs(a, n)); // This code is contributed by unknown2108 </script>
4
Complejidad del tiempo: O(n 5/2 )
Espacio Auxiliar: O(n 2 )
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA