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

Given an array **Arr[]** of **N** ( *1 ≤ N ≤ 10 ^{5}*)integers, the task is to generate an array

**B[]**consisting of

**N non-zero elements**, such that

**XOR**of

**A**^

_{i}**B**always results in a prime number.

_{i}**Note:** The sum of XORs obtained should be minimized.

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**.

**Examples:**

Input:arr[] = {5, 4, 7, 6}Output:{7, 6, 5, 4}Explanation:2is 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 = 2because1. XOR of 5 ^ 7 = 2, which is prime2. 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:

- 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 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;` `}` |

## Java

`// Java implementation of the above approach` `class` `GFG{` `// Function to generate an array whose XOR` `// with same-indexed elements of the given` `// array is always a prime` `private` `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 code` `public` `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 prime` `def` `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 Code` `if` `__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 prime` `private` `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 code` `public` `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 prime` `function` `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)