Comprobar si el XOR de una array de enteros es par o impar

Dada una array arr que contiene números enteros de tamaño N , la tarea es verificar si el XOR de esta array es par o impar .

Ejemplos : 

Entrada: arr[] = { 2, 4, 7} 
Salida: Impar 
Explicación: 
XOR de array = 2 ^ 4 ^ 7 = 1, que es impar

Entrada: arr[] = { 3, 9, 12, 13, 15 } 
Salida: Par 
 

Solución ingenua: primero encuentre el XOR de la array dada de enteros y luego verifique si este XOR es par o impar.

Complejidad de tiempo: O(N)

Solución eficiente: una mejor solución se basa en el hecho de manipulación de bits , que:  

• El XOR bit a bit de dos números pares o dos números impares siempre es par .
• El XOR bit a bit de un número par y un número impar siempre es impar .

Por lo tanto, si el recuento de números impares en la array es impar, el XOR final será impar y, si es par, el XOR final será par.

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

// C++ program to check if the XOR
// of an array is Even or Odd
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the XOR of
// an array of integers is Even or Odd
string check(int arr[], int n)
{
    int count = 0;
 
    for (int i = 0; i < n; i++) {
 
        // Count the number
        // of odd elements
        if (arr[i] & 1)
            count++;
    }
 
    // If count of odd elements
    // is odd, then XOR will be odd
    if (count & 1)
        return "Odd";
 
    // Else even
    else
        return "Even";
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 9, 12, 13, 15 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << check(arr, n) << endl;
 
    return 0;
}

// Java program to check if the XOR
// of an array is Even or Odd
import java.util.*;
 
class GFG{
 
// Function to check if the XOR of
// an array of integers is Even or Odd
static String check(int []arr, int n)
{
    int count = 0;
 
    for (int i = 0; i < n; i++) {
 
        // Count the number
        // of odd elements
        if ((arr[i] & 1)!=0)
            count++;
    }
 
    // If count of odd elements
    // is odd, then XOR will be odd
    if ((count & 1)!=0)
        return "Odd";
 
    // Else even
    else
        return "Even";
}
 
// Driver Code
public static void main(String args[])
{
    int []arr = { 3, 9, 12, 13, 15 };
    int n = arr.length;
 
    // Function call
    System.out.println(check(arr, n));
}
}
 
// This code is contributed by Surendra_Gangwar

# Python3 program to check if the XOR
# of an array is Even or Odd
 
# Function to check if the XOR of
# an array of integers is Even or Odd
def check(arr, n):
    count = 0;
 
    for i in range(n):
 
        # Count the number
        # of odd elements
        if (arr[i] & 1):
            count = count + 1;
     
    # If count of odd elements
    # is odd, then XOR will be odd
    if (count & 1):
        return "Odd";
 
    # Else even
    else:
        return "Even";
 
# Driver Code
if __name__=='__main__':
 
    arr = [ 3, 9, 12, 13, 15 ]
    n = len(arr)
 
    # Function call
    print(check(arr, n))
 
 
# This code is contributed by Princi Singh

// C# program to check if the XOR
// of an array is Even or Odd
using System;
using System.Collections.Generic;
using System.Linq;
  
class GFG
{
 
// Function to check if the XOR of
// an array of integers is Even or Odd
static String check(int []arr, int n)
{
    int count = 0;
 
    for (int i = 0; i < n; i++) {
 
        // Count the number
        // of odd elements
        if (arr[i] == 1)
            count++;
    }
 
    // If count of odd elements
    // is odd, then XOR will be odd
    if (count == 1)
        return "Odd";
 
    // Else even
    else
        return "Even";
}
 
// Driver Code
    public static void Main(String[] args)
    {
    int []arr= { 3, 9, 12, 13, 15 };
    int n = arr.Length;
 
    // Function call
    Console.Write(check(arr, n));
}
}
 
// This code is contributed by shivanisinghss2110

<script>
 
// Javascript program to check if the XOR
// of an array is Even or Odd
 
// Function to check if the XOR of
// an array of integers is Even or Odd
function check(arr, n)
{
    let count = 0;
 
    for(let i = 0; i < n; i++)
    {
         
        // Count the number
        // of odd elements
        if (arr[i] & 1)
            count++;
    }
 
    // If count of odd elements
    // is odd, then XOR will be odd
    if (count & 1)
        return "Odd";
 
    // Else even
    else
        return "Even";
}
 
// Driver Code
let arr = [ 3, 9, 12, 13, 15 ];
let n = arr.length;
 
// Function call
document.write(check(arr, n));
 
// This code is contributed by subham348
 
</script>

Even

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