Compruebe si el OR bit a bit de N números es par o impar

Dada una array arr[] que contiene N números. La tarea es verificar si el OR bit a bit de los N números dados es par o impar.
Ejemplos : 
 

Input : arr[] = { 2, 12, 20, 36, 38 }
Output : Even Bit-wise OR

Input : arr[] = { 3, 9, 12, 13, 15 }
Output : Odd Bit-wise OR

Una solución simple es primero encontrar el OR de los N números dados, luego verificar si este OR es par o impar.
Complejidad de tiempo: O(N)
Una mejor solución se basa en la manipulación de bits y hechos matemáticos. 
 

• Bitwise OR de dos números pares cualesquiera es un número par. 
   
• Bitwise OR de cualquier número impar es un número impar. 
   
• Bitwise OR de un número par y un número impar es un número impar. 
   

Con base en los hechos anteriores, se puede deducir que si al menos un número impar está presente en la array, el OR bit a bit de toda la array será impar, de lo contrario, será par.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation to check whether
// bitwise OR of n numbers is even or odd
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if bitwise OR
// of n numbers is even or odd
bool check(int arr[], int n)
{
    for (int i = 0; i < n; i++) {
        // if at least one odd number is found,
        // then the bitwise OR of all numbers will be odd
        if (arr[i] & 1)
            return true;
    }
 
    // Bitwise OR is an odd number
    return false;
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 9, 12, 13, 15 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    if (check(arr, n))
        cout << "Odd Bit-wise OR";
    else
        cout << "Even Bit-wise OR";
    return 0;
}

// Java implementation to check whether
// bitwise OR of n numbers is even or odd
class GFG
{
 
// Function to check if bitwise OR
// of n numbers is even or odd
static boolean check(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        // if at least one odd number is
        // found, then the bitwise OR of
        // all numbers will be odd
        if (arr[i] % 2 == 1)
        {
            return true;
        }
    }
 
    // Bitwise OR is an odd number
    return false;
}
 
// Driver Code
public static void main(String args[])
{
    int arr[] = {3, 9, 12, 13, 15};
    int n = arr.length;
 
    if (check(arr, n))
    {
        System.out.println("Odd Bit-wise OR");
    }
    else
    {
        System.out.println("Even Bit-wise OR");
    }
}
}
 
// This code is contributed
// by 29AjayKumar

# Python3 implementation to check whether
# bitwise OR of n numbers is even or odd
 
# Function to check if bitwise OR
# of n numbers is even or odd
def check(arr,n):
    for i in range(n):
 
        # if at least one odd number is found,
        # then the bitwise OR of all numbers
        # will be odd
        if arr[i] & 1:
            return True
 
    # Bitwise OR is an odd number
    return False
 
# Driver code
if __name__=='__main__':
    arr = [3, 9, 12, 13, 15]
    n = len(arr)
    if check(arr,n):
        print("Odd Bit-wise OR")
    else:
        print("Even Bit-wise OR")
 
# This code is contributed by
# Shrikant13

// C# implementation to check whether
// bitwise OR of n numbers is even or odd
using System;
 
class GFG
{
 
// Function to check if bitwise OR
// of n numbers is even or odd
static bool check(int []arr, int n)
{
    for (int i = 0; i < n; i++)
    {
        // if at least one odd number is
        // found, then the bitwise OR of
        // all numbers will be odd
        if (arr[i] % 2 == 1)
        {
            return true;
        }
    }
 
    // Bitwise OR is an odd number
    return false;
}
 
// Driver Code
public static void Main()
{
    int []arr = {3, 9, 12, 13, 15};
    int n = arr.Length;
 
    if (check(arr, n))
    {
        Console.WriteLine("Odd Bit-wise OR");
    }
    else
    {
        Console.WriteLine("Even Bit-wise OR");
    }
}
}
 
// This code is contributed
// by 29AjayKumar

<?php
//PHp implementation to check whether
// bitwise OR of n numbers is even or odd
 
// Function to check if bitwise OR
// of n numbers is even or odd
 
function  check($arr, $n)
{
    for ($i = 0; $i < $n; $i++) {
        // if at least one odd number is found,
        // then the bitwise OR of all numbers will be odd
        if ($arr[$i] & 1)
            return true;
    }
 
    // Bitwise OR is an odd number
    return false;
}
 
// Driver Code
 
    $arr = array (3, 9, 12, 13, 15 );
     $n = sizeof($arr) / sizeof($arr[0]);
 
    if (check($arr, $n))
         echo  "Odd Bit-wise OR";
    else
        echo "Even Bit-wise OR";
     
// This code is contributed by ajit
?>

<script>
 
// Javascript implementation to check whether
// bitwise OR of n numbers is even or odd
 
// Function to check if bitwise OR
// of n numbers is even or odd
function check(arr, n)
{
    for (let i = 0; i < n; i++)
    {
     
        // if at least one odd number is found,
        // then the bitwise OR of all numbers will be odd
        if (arr[i] & 1)
            return true;
    }
 
    // Bitwise OR is an odd number
    return false;
}
 
// Driver Code
    let arr = [ 3, 9, 12, 13, 15 ];
    let n = arr.length;
 
    if (check(arr, n))
        document.write("Odd Bit-wise OR");
    else
        document.write("Even Bit-wise OR");
 
// This code is contributed by rishavmahato348.
</script>

Odd Bit-wise OR

Complejidad de tiempo : O(N) en el peor de los casos.