Given an array Arr[] of N ( 1 ? N ? 105)integers, the task is to generate an array B[] consisting of N non-zero elements, such that XOR of Ai ^ Bi always results in a prime number.
Note: The sum of XORs obtained should be minimized.
Examples:
Input: arr[] = {5, 4, 7, 6}
Output: {7, 6, 5, 4}
Explanation:
2 is the smallest prime number. Therefore, XORing A[i] with (A[i] ^ 2)
gives us the smallest number which is prime.
A[i] ^ (A[i] ^ 2) = (A[i] ^ A[i]) ^ 2 = 0 ^ 2 = 2
because
1. XOR of 5 ^ 7 = 2, which is prime
2. XOR of 4 ^ 6 = 2, which is prime.
3. XOR of 7 ^ 5 = 2, which is prime.
4. XOR of 6 ^ 4 = 2, which is prime.
The resultant sum is – 2 + 2 + 2 + 2 = 8, which is the minimum possibleInput: arr[] = {10, 16}
Output: {8, 18}
Approach: This problem can be solved using a Greedy technique. Follow the steps below to solve the problem:
- Since 2 is the smallest prime number possible, XOR of Arr[i] with B[i] = (Arr[i] ^ 2) will give us a prime number 2.
- The contradiction arises when any of the array elements itself is Arr[i] = 2. In this case, B[i] = 2 ^ 2 results in 0.
- Therefore, if Arr[i] = 2, set B[i] = (2 ^ 3) = 1, such that Arr[i] ^ K = 3, next smallest prime number.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to generate an array whose XOR// with same-indexed elements of the given// array is always a primevoid minXOR(vector<int>& Arr, int N){ // Traverse the array for (int i = 0; i < N; i++) { // If current array element is 2 if (Arr[i] == 2) { // Print its XOR with 3 cout << (Arr[i] ^ 3) << " "; } // Otherwise else { // Print its XOR with 2 cout << (Arr[i] ^ 2) << " "; } }}// Driver Codeint main(){ // Given array vector<int> Arr = { 5, 4, 7, 6 }; // Size of the array int N = Arr.size(); // Prints the required array minXOR(Arr, N); return 0;} |
Java
// Java implementation of the above approachclass GFG{// Function to generate an array whose XOR// with same-indexed elements of the given// array is always a primeprivate static void minXOR(int Arr[], int N){ // Traverse the array for(int i = 0; i < N; i++) { // If current array element is 2 if (Arr[i] == 2) { // Print its XOR with 3 System.out.print((Arr[i] ^ 3) + " "); } // Otherwise else { // Print its XOR with 2 System.out.print((Arr[i] ^ 2) + " "); } }}// Driver codepublic static void main(String[] args){ // Given array int Arr[] = { 5, 4, 7, 6 }; // Size of the array int N = Arr.length; // Prints the required array minXOR(Arr, N);}}// This code is contributed by MuskanKalra1 |
Python3
# Python3 implementation of the above approach # Function to generate an array whose XOR# with same-indexed elements of the given# array is always a primedef minXOR(Arr, N): # Traverse the array for i in range(N): # If current array element is 2 if (Arr[i] == 2): # Print its XOR with 3 print(Arr[i] ^ 3,end=" ") # Otherwise else: # Print its XOR with 2 print(Arr[i] ^ 2,end=" ") # Driver Codeif __name__ == '__main__': # Given array Arr = [5, 4, 7, 6 ] # Size of the array N = len(Arr) # Prints the required array minXOR(Arr, N) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approach using System;class GFG{// Function to generate an array whose XOR// with same-indexed elements of the given// array is always a primeprivate static void minXOR(int[] Arr, int N){ // Traverse the array for(int i = 0; i < N; i++) { // If current array element is 2 if (Arr[i] == 2) { // Print its XOR with 3 Console.Write((Arr[i] ^ 3) + " "); } // Otherwise else { // Print its XOR with 2 Console.Write((Arr[i] ^ 2) + " "); } }}// Driver codepublic static void Main(){ // Given array int[] Arr = { 5, 4, 7, 6 }; // Size of the array int N = Arr.Length; // Prints the required array minXOR(Arr, N);}} |
Javascript
<script>// JavaScript implementation of the above approach// Function to generate an array whose XOR// with same-indexed elements of the given// array is always a primefunction minXOR(Arr, N){ // Traverse the array for(let i = 0; i < N; i++) { // If current array element is 2 if (Arr[i] == 2) { // Print its XOR with 3 document.write((Arr[i] ^ 3) + " "); } // Otherwise else { // Print its XOR with 2 document.write((Arr[i] ^ 2) + " "); } }}// Driver code // Given array let Arr = [ 5, 4, 7, 6 ]; // Size of the array let N = Arr.length; // Prints the required array minXOR(Arr, N); </script> |
Output:
7 6 5 4
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
