Count Pairs with XOR Representable as Sum of Same Parity Primes
Given an array A[] of length N, the task is to count the number of distinct pairs of indices (i, j), such that, (A[i] XOR A[j]) can be expressed as the sum of two prime numbers of the same parity.
Examples:
Input: N = 5, A[] = {2, 4, 8, 1, 3}
Output: 3
Explanation: There are total three such pairs:
- (0, 1) => A[0] XOR A[1] = 2 XOR 4 = 6 and 6 can be expressed as sum of two prime numbers of same parity (3 + 3)
- (0, 2) => A[0] XOR A[2] = 2 XOR 8 = 10 and 10 can be expressed as sum of two prime numbers of same parity (3 + 7)
- (1, 2) => A[1] XOR A[2] = 4 XOR 8 = 12 and 12 can be expressed as sum of two prime numbers of same parity (5 + 7).
Input: N = 3, A[] = {1, 1, 3}
Output: 0
Explanation: It can be verified that there are no pairs following the given conditions. Therefore, output is 0.
Approach: Implement the idea below to solve the problem
Observations:
- The sum of any two numbers of the same parity is an even Number. Therefore, the XOR should be an even number.
- Among all the even numbers, 0 and 2 cannot be represented as the sum of two prime numbers.
- All even numbers greater than 2 can be represented as the sum of two prime numbers (Goldbach’s Conjecture)
From the above observations, we simply need to find number of pairs (i, j) such that their XOR is an Even number greater than 2. The XOR of two numbers is even only if both the numbers are of same parity. So, we can count all the pairs having Even XOR by pairing all the Odd numbers among themselves and all the Even numbers among themselves. Finally, we need to subtract those pairs whose XOR is 0 or 2.
- For XOR = 0, both the numbers should be same so we can count the frequency of all the elements in a frequency array and calculate the count of such pairs.
- For XOR = 2, we can simply use the frequency array to count such pairs.
Steps to solve the problem:
- Create two variables even, odd to count odd and even elements.
- Declare a map let say freq_arr for counting frequencies of elements.
- Run a loop for initializing map, odd and even.
- Initialize a variable ans = (even * (even – 1))/2 + (odd * (odd – 1))/2, to store the total number of pairs whose XOR is Even.
- Iterate over freq_arr
- Subtract the number of pairs whose XOR is 0 from ans
- Subtract the number of pairs whose XOR is 2 from ans
- Replace the frequency array of current element as 0, to prevent counting them twice (while counting pairs whose XOR is 2)
- Return ans as the final answer
Below is the implementation of the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Method to print the number of pairs void CountPairs( int N, vector< int >& A) { // Variables to count odd and even elements and the // final answer int even = 0, odd = 0, ans = 0; // Declare an unordered_map to store the frequency of // elements unordered_map< int , int > freq_arr; // Loop for initializing the map and odd, even variables for ( int i = 0; i < N; i++) { freq_arr[A[i]]++; if (A[i] % 2 == 1) odd++; else even++; } // Count all the pairs having even XOR ans = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2; // Implementing the approach for ( const auto & i : freq_arr) { // Subtract all pairs having XOR = 0 ans -= (i.second * (i.second - 1)) / 2; // Subtract all pairs having XOR = 2 ans -= i.second * freq_arr[i.first ^ 2]; // To prevent counting the pairs twice freq_arr[i.first] = 0; } // Printing the number of pairs cout << ans << endl; } int main() { // Inputs int N = 5; vector< int > A = { 2, 4, 8, 1, 3 }; // Function call CountPairs(N, A); return 0; } // This code is contributed by Abhinav Mahajan // (abhinav_m22). |
Java
// Java code to implement the approach import java.util.*; public class GFG { // Driver Function public static void main(String[] args) { // Inputs Integer N = 5 ; Integer[] A = { 2 , 4 , 8 , 1 , 3 }; // Function call Count_Pairs(N, A); } // Method to print the number of pairs public static void Count_Pairs(Integer N, Integer[] A) { // Variables to count odd and even // elements and the final answer Integer even = 0 , odd = 0 , ans = 0 ; // Declared a Map to store the // frequency of element Map<Integer, Integer> freq_arr = new HashMap<>(); // Loop for initializing map and odd, // even variables for (Integer i = 0 ; i < N; i++) { freq_arr.put( A[i], freq_arr.getOrDefault(A[i], 0 ) + 1 ); if ((A[i] & 1 ) == 1 ) odd++; else even++; } // Count all the pairs having even XOR ans = (even * (even - 1 )) / 2 + (odd * (odd - 1 )) / 2 ; // Implementing the approach for (Map.Entry<Integer, Integer> i : freq_arr.entrySet()) { // Subtract all pairs having XOR = 0 ans -= (i.getValue() * (i.getValue() - 1 )) / 2 ; // Subtract all pairs having XOR = 2 ans -= (i.getValue() * freq_arr.getOrDefault(i.getKey() ^ 2 , 0 )); // To prevent counting the pairs twice freq_arr.put(i.getKey(), 0 ); } // Printing the number of pairs System.out.println(ans); } } |
Python3
def CountPairs(N, A): # Variables to count odd and even elements and the final answer even = 0 odd = 0 ans = 0 # Declare a dictionary to store the frequency of elements freq_arr = {} # Loop for initializing dictionary and odd, even variables for i in range (N): freq_arr[A[i]] = freq_arr.get(A[i], 0 ) + 1 if A[i] % 2 = = 1 : odd + = 1 else : even + = 1 # Count all the pairs having even XOR ans = (even * (even - 1 )) / 2 + (odd * (odd - 1 )) / 2 # Implementing the approach for key, value in freq_arr.items(): # Subtract all pairs having XOR = 0 ans - = (value * (value - 1 )) / 2 # Subtract all pairs having XOR = 2 ans - = value * freq_arr.get(key ^ 2 , 0 ) # To prevent counting the pairs twice freq_arr[key] = 0 # Returning the number of pairs return ans # Driver function if __name__ = = '__main__' : N = 5 A = [ 2 , 4 , 8 , 1 , 3 ] # Function call ans = CountPairs(N, A) # Printing the number of pairs print (ans) #This code is contributed by Rohit Singh |
C#
// C# Code using System; using System.Collections.Generic; class GFG { // Method to print the number of pairs static double CountPairs( int N, List< int > A) { // Variables to count odd and even elements and the // final answer int even = 0; int odd = 0; double ans = 0; // Declare a Dictionary to store the frequency of // elements Dictionary< int , int > freqArr = new Dictionary< int , int >(); // Loop for initializing the Dictionary and odd, even variables for ( int i = 0; i < N; i++) { freqArr[A[i]] = freqArr.TryGetValue(A[i], out int value) ? value + 1 : 1; if (A[i] % 2 == 1) odd++; else even++; } // Count all the pairs having even XOR ans = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2; // Implementing the approach foreach ( var key in new List< int >(freqArr.Keys)) { // Subtract all pairs having XOR = 0 ans -= (freqArr[key] * (freqArr[key] - 1)) / 2; // Subtract all pairs having XOR = 2 ans -= freqArr[key] * freqArr.GetValueOrDefault(key ^ 2, 0); // To prevent counting the pairs twice freqArr[key] = 0; } // Returning the number of pairs return ans; } // Driver Function static void Main() { // Inputs int N = 5; List< int > A = new List< int > { 2, 4, 8, 1, 3 }; // Function call double ans = CountPairs(N, A); // Printing the number of pairs Console.WriteLine(ans); } } |
Javascript
// Javascript code for the above approach // Method to print the number of pairs function countPairs(N, A) { // Variables to count odd and even elements and the // final answer let even = 0, odd = 0, ans = 0; // Declare an map to store the frequency of // elements const freqArr = new Map(); // Loop for initializing the map and odd, even variables for (let i = 0; i < N; i++) { if (!freqArr.has(A[i])) { freqArr.set(A[i], 1); } else { freqArr.set(A[i], freqArr.get(A[i]) + 1); } if (A[i] % 2 === 1) { odd++; } else { even++; } } // Count all the pairs having even XOR ans = (even * (even - 1)) / 2 + (odd * (odd - 1)) / 2; // Implementing the approach for (const [key, value] of freqArr) { // Subtract all pairs having XOR = 0 ans -= (value * (value - 1)) / 2; // Subtract all pairs having XOR = 2 ans -= value * (freqArr.get(key ^ 2) || 0); // To prevent counting the pairs twice freqArr.set(key, 0); } // Printing the number of pairs console.log(ans); } // Inputs const N = 5; const A = [2, 4, 8, 1, 3]; // Function call countPairs(N, A); |
3
Time Complexity: O(N), where N is the size of input array A[]
Auxiliary Space: O(N)