Cuente los pares con Bitwise XOR impar que se pueden eliminar y reemplazar por su Bitwise OR

Dada una array arr[] que consta de N enteros, la tarea es contar el número de pares cuyo Bitwise XOR es impar, que se pueden eliminar y reemplazar por sus valores Bitwise OR hasta que no exista tal par en la array.

Ejemplos:

Entrada: arr[] = {5, 4, 7, 2}
Salida: 2
Explicación:
Par (5, 4): Bitwise XOR de 5 y 4 es 1. Quite este par y agregue su Bitwise OR (= 5) en el formación. Por lo tanto, la array modificada es {5, 7, 2}.
Par (5, 2): Bitwise XOR de 5 y 2 es 7. Elimine este par y agregue su Bitwise OR (= 7) en la array. Por lo tanto, la array modificada es {7, 7}.

Por lo tanto, la cantidad de pares que se pueden eliminar es 2.

Entrada: arr[] = {2, 4, 6}
Salida: 0

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

• El XOR bit a bit de un par es impar solo si un elemento es impar y el otro es par .
• Por lo tanto, eliminar dicho par de la array y agregar su Bitwise OR en la array no afecta el recuento total de elementos impares en la array . Pero el recuento de elementos pares de la array se reduce en 1 .

Por lo tanto, la idea es encontrar el conteo de elementos pares presentes en la array dada . Si el recuento de elementos pares es N , se requieren 0 movimientos. De lo contrario, imprima el valor de conteo como el conteo resultante de pares que se deben eliminar.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number of pairs
// required to be removed from the array
// and replaced by their Bitwise OR values
void countPairs(int arr[], int N)
{
    // Stores the count of
    // even array elements
    int even = 0;
 
    // Traverse the given array
    for (int i = 0; i < N; i++) {
 
        // Increment the count
        // of even array elements
        if (arr[i] % 2 == 0)
            even++;
    }
 
    // If the array contains at
    // least one odd array element
    if (N - even >= 1) {
        cout << even;
        return;
    }
 
    // Otherwise, print 0
    cout << 0;
}
 
// Driver Code
int main()
{
    int arr[] = { 5, 4, 7, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
    countPairs(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to count the number of pairs
// required to be removed from the array
// and replaced by their Bitwise OR values
static void countPairs(int arr[], int N)
{
     
    // Stores the count of
    // even array elements
    int even = 0;
 
    // Traverse the given array
    for(int i = 0; i < N; i++)
    {
         
        // Increment the count
        // of even array elements
        if (arr[i] % 2 == 0)
            even++;
    }
 
    // If the array contains at
    // least one odd array element
    if (N - even >= 1)
    {
        System.out.println(even);
        return;
    }
 
    // Otherwise, print 0
    System.out.println(0);
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 5, 4, 7, 2 };
    int N = arr.length;
 
    countPairs(arr, N);
}
}
 
// This code is contributed by Kingash

# Python3 program for the above approach
 
# Function to count the number of pairs
# required to be removed from the array
# and replaced by their Bitwise OR values
def countPairs(arr, N):
 
    # Stores the count of
    # even array elements
    even = 0
 
    # Traverse the given array
    for i in range(N):
 
        # Increment the count
        # of even array elements
        if (arr[i] % 2 == 0):
            even += 1
     
    # If the array contains at
    # least one odd array element
    if (N - even >= 1):
        print(even)
        return
 
    # Otherwise, print 0
    print(0)
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 5, 4, 7, 2 ]
    N = len(arr)
     
    countPairs(arr, N)
 
# This code is contributed by AnkThon

// C# program for the above approach
using System;
 
class GFG{
     
// Function to count the number of pairs
// required to be removed from the array
// and replaced by their Bitwise OR values
static void countPairs(int[] arr, int N)
{
     
    // Stores the count of
    // even array elements
    int even = 0;
 
    // Traverse the given array
    for(int i = 0; i < N; i++)
    {
         
        // Increment the count
        // of even array elements
        if (arr[i] % 2 == 0)
            even++;
    }
 
    // If the array contains at
    // least one odd array element
    if (N - even >= 1)
    {
        Console.WriteLine(even);
        return;
    }
 
    // Otherwise, print 0
    Console.WriteLine(0);
}
 
// Driver code
static void Main()
{
    int[] arr = { 5, 4, 7, 2 };
    int N = arr.Length;
 
    countPairs(arr, N);
}
}
 
// This code is contributed by sanjoy_62

<script>
 
// JavaScript program for the above approach
 
// Function to count the number of pairs
// required to be removed from the array
// and replaced by their Bitwise OR values
function countPairs(arr, N)
{
    // Stores the count of
    // even array elements
    let even = 0;
 
    // Traverse the given array
    for (let i = 0; i < N; i++) {
 
        // Increment the count
        // of even array elements
        if (arr[i] % 2 == 0)
            even++;
    }
 
    // If the array contains at
    // least one odd array element
    if (N - even >= 1) {
        document.write(even);
        return;
    }
 
    // Otherwise, print 0
    document.write(0);
}
 
// Driver Code
let arr = [ 5, 4, 7, 2 ];
let N = arr.length;
countPairs(arr, N);
 
</script>

2

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