Genere una array de suma mínima cuyo XOR de elementos del mismo índice con una array dada sean números primos

Dada una array Arr[] de N ( 1 ≤ N ≤ 10 ⁵ ) enteros, la tarea es generar una array B[] que consta de N elementos distintos de cero , tal que XOR de A _i ^ B _i siempre da como resultado un número primo número. 

Nota: La suma de los XOR obtenidos debe minimizarse.

Ejemplos:

Entrada: arr[] = {5, 4, 7, 6} 
Salida: {7, 6, 5, 4} 
Explicación:  
2 es el número primo más pequeño. Por lo tanto, XORing A[i] con (A[i] ^ 2) 
nos da el número más pequeño que es primo.  
A[i] ^ (A[i] ^ 2) = (A[i] ^ A[i]) ^ 2 = 0 ^ 2 = 2 
porque 
1. XOR de 5 ^ 7 = 2, que es primo 
2. XOR de 4^6 = 2, que es primo. 
3. XOR de 7^5 = 2, que es primo. 
4. XOR de 6^4 = 2, que es primo. 
La suma resultante es – 2 + 2 + 2 + 2 = 8, que es el mínimo posible

Entrada: arr[] = {10, 16} 
Salida: {8, 18}

Enfoque: Este problema se puede resolver usando una técnica Greedy . Siga los pasos a continuación para resolver el problema:

1. Dado que 2 es el número primo más pequeño posible, XOR de Arr[i] con B[i] = (Arr[i] ^ 2) nos dará un número primo 2 .
2. La contradicción surge cuando cualquiera de los elementos de la array es Arr[i] = 2 . En este caso, B[i] = 2 ^ 2 da como resultado 0 .
3. Por lo tanto, si Arr[i] = 2 , establecer B[i] = (2 ^ 3) = 1 , tal que Arr[i] ^ K = 3 , el siguiente número primo más pequeño.

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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);
}
}

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

7 6 5 4

Complejidad temporal: O(N) 
Espacio auxiliar: O(1)