Compruebe si la array original se conserva después de realizar XOR con M exactamente K veces

Dada una array A y dos enteros M y K , la tarea es verificar e imprimir » Sí «, si la array original se puede conservar realizando exactamente el número ‘ K ‘ de operaciones XOR bit a bit de los elementos de la array con ‘ M ‘. De lo contrario, escriba » No «.
Nota: la operación XOR se puede realizar, en cualquier elemento de la array, 0 o más veces. 
Ejemplos: 
 

Entrada: A[] = {1, 2, 3, 4}, M = 5, K = 6 
Salida: Sí 
Explicación: 
Si el XOR se realiza en el primer elemento, A[0], 6 veces, obtenemos A[ 0] atrás. Por lo tanto, se conserva la array original.
Entrada: A[] = {5, 9, 3, 4, 5}, M = 5, K = 3 
Salida: No 
Explicación: 
La array original no se puede conservar después de realizar un número impar de operaciones XOR. 
 

Enfoque: este problema se puede resolver usando la propiedad XOR 
 

A X O B = C y C X O B = A 
 

Se puede ver que: 
 

1. si se realiza un número par de operaciones XOR para cualquier número positivo, entonces se puede conservar el número original.
2. Sin embargo, 0 es una excepción. Si se realiza un número par o impar de operaciones XOR para 0, entonces se puede conservar el número original.
3. Por lo tanto, si K es par y M es 0 , entonces la respuesta siempre será Sí.
4. Si K es impar y 0 no está presente en la array , la respuesta siempre será No.
5. Si K es impar y la cuenta de 0 es al menos 1 en la array, la respuesta será Sí.

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

// C++ implementation for the
// above mentioned problem
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if original Array
// can be retained by performing XOR
// with M exactly K times
string check(int Arr[], int n,
             int M, int K)
{
    int flag = 0;
 
    // Check if O is present or not
    for (int i = 0; i < n; i++) {
        if (Arr[i] == 0)
            flag = 1;
    }
 
    // If K is odd and 0 is not present
    // then the answer will always be No.
    if (K % 2 != 0
        && flag == 0)
        return "No";
 
    // Else it will be Yes
    else
        return "Yes";
}
 
// Driver Code
int main()
{
 
    int Arr[] = { 1, 1, 2, 4, 7, 8 };
    int M = 5;
    int K = 6;
    int n = sizeof(Arr) / sizeof(Arr[0]);
 
    cout << check(Arr, n, M, K);
    return 0;
}

import java.util.*;
 
class GFG{
 
// Function to check if original Array
// can be retained by performing XOR
// with M exactly K times
static String check(int []Arr, int n,
            int M, int K)
{
    int flag = 0;
 
    // Check if O is present or not
    for (int i = 0; i < n; i++) {
        if (Arr[i] == 0)
            flag = 1;
    }
 
    // If K is odd and 0 is not present
    // then the answer will always be No.
    if (K % 2 != 0
        && flag == 0)
        return "No";
 
    // Else it will be Yes
    else
        return "Yes";
}
 
// Driver Code
public static void main(String args[])
{
 
    int []Arr = { 1, 1, 2, 4, 7, 8 };
    int M = 5;
    int K = 6;
    int n = Arr.length;
 
    System.out.println(check(Arr, n, M, K));
}
}
 
// This code is contributed by Surendra_Gangwar

# Python3 implementation for the
# above mentioned problem
  
# Function to check if original Array
# can be retained by performing XOR
# with M exactly K times
def check(Arr,  n, M,  K):
    flag = 0
  
    # Check if O is present or not
    for i in range(n):
        if (Arr[i] == 0):
            flag = 1
     
    # If K is odd and 0 is not present
    # then the answer will always be No.
    if (K % 2 != 0 and flag == 0):
        return "No"
  
    # Else it will be Yes
    else:
        return "Yes";
  
# Driver Code
if __name__=='__main__':
 
    Arr = [ 1, 1, 2, 4, 7, 8 ]
    M = 5;
    K = 6;
    n = len(Arr);
  
    print(check(Arr, n, M, K))
 
# This article contributed by Princi Singh

// C# implementation for the
// above mentioned problem
using System;
   
class GFG
{
   
 
// Function to check if original Array
// can be retained by performing XOR
// with M exactly K times
static String check(int []Arr, int n,int M, int K)
{
    int flag = 0;
 
    // Check if O is present or not
    for (int i = 0; i < n; i++) {
        if (Arr[i] == 0)
            flag = 1;
    }
 
    // If K is odd and 0 is not present
    // then the answer will always be No.
    if (K % 2 != 0
        && flag == 0)
        return "No";
 
    // Else it will be Yes
    else
        return "Yes";
}
 
// Driver code
public static void Main(String[] args)
{
 
    int []Arr = { 1, 1, 2, 4, 7, 8 };
    int M = 5;
    int K = 6;
    int n = Arr.Length;
 
    Console.Write(check(Arr, n, M, K));
}
}
 
// This code is contributed by shivanisinghss2110

<script>
// Javascript implementation for the
// above mentioned problem
 
// Function to check if original Array
// can be retained by performing XOR
// with M exactly K times
function check(Arr, n, M, K)
{
    let flag = 0;
 
    // Check if O is present or not
    for (let i = 0; i < n; i++) {
        if (Arr[i] == 0)
            flag = 1;
    }
 
    // If K is odd and 0 is not present
    // then the answer will always be No.
    if (K % 2 != 0
        && flag == 0)
        return "No";
 
    // Else it will be Yes
    else
        return "Yes";
}
 
// Driver Code
 
    let Arr = [ 1, 1, 2, 4, 7, 8 ];
    let M = 5;
    let K = 6;
    let n = Arr.length;
 
    document.write(check(Arr, n, M, K));
 
</script>

Yes

Complejidad de tiempo: O(N), ya que estamos usando un bucle para atravesar N veces, por lo que nos costará O(N) tiempo 
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio adicional.