Given an array arr of integers of size N and an integer K, the task is to find the XOR of all the numbers which are prime and at a position divisible by K.
Examples:
Input: arr[] = {2, 3, 5, 7, 11, 8}, K = 2
Output: 4
Explanation:
Positions which are divisible by K are 2, 4, 6 and the elements are 3, 7, 8.
3 and 7 are primes among these.
Therefore XOR = 3 ^ 7 = 4Input: arr[] = {1, 2, 3, 4, 5}, K = 3
Output: 3
Naive Approach: Traverse the array and for every position i which is divisible by k, check if it is prime or not. If it is a prime then compute the XOR of this number with the previous answer.
Efficient Approach: An efficient approach is to use Sieve Of Eratosthenes. Sieve array can be used to check a number is prime or not in O(1) time.
Below is the implementation of the above approach:
C++
// C++ program to find XOR of// all Prime numbers in an Array// at positions divisible by K#include <bits/stdc++.h>using namespace std;#define MAX 1000005void SieveOfEratosthenes(vector<bool>& prime){ // 0 and 1 are not prime numbers prime[1] = false; prime[0] = false; for (int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2; i < MAX; i += p) prime[i] = false; } }}// Function to find the required XORvoid prime_xor(int arr[], int n, int k){ vector<bool> prime(MAX, true); SieveOfEratosthenes(prime); // To store XOR of the primes long long int ans = 0; // Traverse the array for (int i = 0; i < n; i++) { // If the number is a prime if (prime[arr[i]]) { // If index is divisible by k if ((i + 1) % k == 0) { ans ^= arr[i]; } } } // Print the xor cout << ans << endl;}// Driver codeint main(){ int arr[] = { 2, 3, 5, 7, 11, 8 }; int n = sizeof(arr) / sizeof(arr[0]); int K = 2; // Function call prime_xor(arr, n, K); return 0;} |
Java
// Java program to find XOR of// all Prime numbers in an Array// at positions divisible by Kclass GFG { static int MAX = 1000005; static boolean prime[] = new boolean[MAX]; static void SieveOfEratosthenes(boolean []prime) { // 0 and 1 are not prime numbers prime[1] = false; prime[0] = false; for (int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2;i < MAX; i += p) prime[i] = false; } } } // Function to find the required XOR static void prime_xor(int arr[], int n, int k) { for(int i = 0; i < MAX; i++) prime[i] = true; SieveOfEratosthenes(prime); // To store XOR of the primes int ans = 0; // Traverse the array for (int i = 0; i < n; i++) { // If the number is a prime if (prime[arr[i]]) { // If index is divisible by k if ((i + 1) % k == 0) { ans ^= arr[i]; } } } // Print the xor System.out.println(ans); } // Driver code public static void main (String[] args) { int arr[] = { 2, 3, 5, 7, 11, 8 }; int n = arr.length; int K = 2; // Function call prime_xor(arr, n, K); }}// This code is contributed by Yash_R |
Python3
# Python3 program to find XOR of # all Prime numbers in an Array # at positions divisible by K MAX = 1000005def SieveOfEratosthenes(prime) : # 0 and 1 are not prime numbers prime[1] = False; prime[0] = False; for p in range(2, int(MAX ** (1/2))) : # If prime[p] is not changed, # then it is a prime if (prime[p] == True) : # Update all multiples of p for i in range(p * 2, MAX, p) : prime[i] = False; # Function to find the required XOR def prime_xor(arr, n, k) : prime = [True]*MAX ; SieveOfEratosthenes(prime); # To store XOR of the primes ans = 0; # Traverse the array for i in range(n) : # If the number is a prime if (prime[arr[i]]) : # If index is divisible by k if ((i + 1) % k == 0) : ans ^= arr[i]; # Print the xor print(ans); # Driver code if __name__ == "__main__" : arr = [ 2, 3, 5, 7, 11, 8 ]; n = len(arr); K = 2; # Function call prime_xor(arr, n, K); # This code is contributed by Yash_R |
C#
// C# program to find XOR of// all Prime numbers in an Array// at positions divisible by Kusing System;class GFG { static int MAX = 1000005; static bool []prime = new bool[MAX]; static void SieveOfEratosthenes(bool []prime) { // 0 and 1 are not prime numbers prime[1] = false; prime[0] = false; for (int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for (int i = p * 2;i < MAX; i += p) prime[i] = false; } } } // Function to find the required XOR static void prime_xor(int []arr, int n, int k) { for(int i = 0; i < MAX; i++) prime[i] = true; SieveOfEratosthenes(prime); // To store XOR of the primes int ans = 0; // Traverse the array for (int i = 0; i < n; i++) { // If the number is a prime if (prime[arr[i]]) { // If index is divisible by k if ((i + 1) % k == 0) { ans ^= arr[i]; } } } // Print the xor Console.WriteLine(ans); } // Driver code public static void Main (string[] args) { int []arr = { 2, 3, 5, 7, 11, 8 }; int n = arr.Length; int K = 2; // Function call prime_xor(arr, n, K); }}// This code is contributed by Yash_R |
Javascript
<script>// Javascript program to find XOR of// all Prime numbers in an Array// at positions divisible by Kconst MAX = 1000005;function SieveOfEratosthenes(prime){ // 0 and 1 are not prime numbers prime[1] = false; prime[0] = false; for(let p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true) { // Update all multiples of p for(let i = p * 2; i < MAX; i += p) prime[i] = false; } }}// Function to find the required XORfunction prime_xor(arr, n, k){ let prime = new Array(MAX).fill(true); SieveOfEratosthenes(prime); // To store XOR of the primes let ans = 0; // Traverse the array for(let i = 0; i < n; i++) { // If the number is a prime if (prime[arr[i]]) { // If index is divisible by k if ((i + 1) % k == 0) { ans ^= arr[i]; } } } // Print the xor document.write(ans);}// Driver codelet arr = [ 2, 3, 5, 7, 11, 8 ];let n = arr.length;let K = 2;// Function callprime_xor(arr, n, K);// This code is contributed by subham348</script> |
Time Complexity: O(N log (log N))
Auxiliary Space: O(?n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
