4

Generate an array of minimum sum whose XOR of same-indexed elements with given a...

 3 years ago
source link: https://www.geeksforgeeks.org/generate-an-array-of-minimum-sum-whose-xor-of-same-indexed-elements-with-given-array-are-prime-numbers/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Improve Article

Generate an array of minimum sum whose XOR of same-indexed elements with given array are Prime Numbers

  • Last Updated : 15 Apr, 2021

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 possible

Input: arr[] = {10, 16} 
Output: {8, 18}

Approach: This problem can be solved using a Greedy technique. Follow the steps below to solve the problem:

  1. 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.
  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.
  3. 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:

  • Python3
  • Javascript
// 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 prime
void 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 Code
int 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;
}
Output: 
7 6 5 4

Time Complexity: O(N) 
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK