Given an array of integers ‘arr’, the task is to find the bitwise XOR of all the prime numbers present in the array.
Examples :
Input : arr[] = {2, 5, 8, 4, 3}
Output : 4
Input : arr[] = {7, 12, 2, 6, 11}
Output : 14
Approach :
-> Create a sieve to check whether an element is prime or not in O(1). -> Traverse the array and check if the number is prime. If it is prime, store it in a vector. -> Then, compute the xor of all the elements of the vector.
Implementation :
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
bool prime[100005];
void SieveOfEratosthenes(int n)
{
memset(prime, true, sizeof(prime));
// false here indicates
// that it is not prime
prime[1] = false;
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p]) {
// Update all multiples of p,
// set them to non-prime
for (int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
}
// Function that computes
// xor of all prime elements
int XOR_OF_PRIMES(int arr[], int n)
{
SieveOfEratosthenes(100004);
// this vector will contain
// prime numbers
vector<int> v;
for (int i = 0; i < n; i++) {
// if the element is prime
if (prime[arr[i]])
v.push_back(arr[i]);
}
int ans;
//initialize ans with fist element of vector
ans = v[0];
for(int j=1;j<v.size();j++)
ans = ans^v[j];
return ans;
}
// Driver code
int main()
{
int arr[] = { 4, 3, 2, 6, 100, 17 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<XOR_OF_PRIMES(arr, n);
return 0;
}
Output :
16