Maximice el recuento de pares cuyo XOR bit a bit es par reemplazando dichos pares con su XOR bit a bit

Dada una array arr[] de tamaño N , la tarea es reemplazar un par de elementos de la array cuyo Bitwise XOR sea par por su Bitwise XOR . Repita el paso anterior el mayor tiempo posible. Finalmente, imprima el recuento de tales operaciones realizadas en la array

Ejemplos:

Entrada: arr[] = { 4, 6, 1, 3 }
Salida: 3
Explicación:
Paso 1: elimine el par (4, 6) y reemplácelo por su valor XOR (= 2) en la array. Por lo tanto, la array arr[] se modifica a {2, 1, 3}.
Paso 2: elimine el par (1, 3) y reemplácelos por su valor XOR (= 2) en la array, modifica la array como arr[] = {2, 2}.
Por último, seleccione el par (2, 2) y luego elimine el par e inserte el xor de 2 y 2 en la array que modifica la array como arr[] ={0}.
Ahora no se puede elegir ningún otro par, por lo tanto, 3 es el número máximo de pares cuyo Xor es par.

Entrada: arr[ ] = { 1, 2, 3, 4, 5 }
Salida: 3

Enfoque ingenuo: el enfoque más simple para resolver este problema es encontrar todos los pares posibles de la array y, para cada par, verificar si su Bitwise XOR es par o no. Si se encuentra que es cierto, entonces incremente el conteo de pares y elimine ambos elementos de la array y agregue su XOR a la array. Repita los pasos anteriores hasta que no se puedan seleccionar más pares. Imprime el recuento de operaciones realizadas. 
Complejidad de tiempo: O(N ³ ), ya que tenemos que usar bucles anidados para atravesar N ³ veces.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:

• Par ^ Par = Par
• Impar ^ Impar = Par
• El número total de pares que se pueden formar a partir de números impares que cumplan las condiciones es impar / 2.
• El número total de pares que se pueden formar a partir de números pares que cumplan las condiciones es par – 1.

Siga los pasos a continuación para resolver el problema:

1. Atraviesa la array .
2. Cuenta la frecuencia de los números impares y guárdala en una variable, digamos impar .
3. El número total de pares con XOR par que se pueden formar a partir de todos los elementos impares del arreglo es floor(odd / 2) .
4. Borrando los pares formados en el paso anterior y reemplazándolos con sus valores XOR respectivamente, aumenta el conteo de elementos pares por piso (impar / 2).
5. Finalmente, imprima el conteo de pares que se pueden formar con par XOR como (N – impar + impar/2 -1) + impar / 2.

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

// C++ program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to maximize the count
// of pairs with even XOR possible
// in an array by given operations
int countPairs(int arr[], int N)
{
    // Stores count of odd
    // array elements
    int odd = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++) {
 
        // If arr[i] is odd
        if (arr[i] & 1)
            odd++;
    }
 
    // Stores the total number
    // of even pairs
    int ans = (N - odd + odd / 2
               - 1)
              + odd / 2;
 
    return ans;
}
 
// Driver Code
int main()
{
    // Input
    int arr[] = { 4, 6, 1, 3 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to count the number
    // of pairs whose XOR is even
    cout << countPairs(arr, N);
 
    return 0;
}

// C program to implement the above approach
#include <stdio.h>
 
// Function to maximize the count
// of pairs with even XOR possible
// in an array by given operations
int countPairs(int arr[], int N)
{
  // Stores count of odd
  // array elements
  int odd = 0;
 
  // Traverse the array
  for (int i = 0; i < N; i++) {
 
    // If arr[i] is odd
    if (arr[i] & 1)
      odd++;
  }
 
  // Stores the total number
  // of even pairs
  int ans = (N - odd + odd / 2
             - 1)
    + odd / 2;
 
  return ans;
}
 
// Driver Code
int main()
{
  // Input
  int arr[] = { 4, 6, 1, 3 };
  int N = sizeof(arr) / sizeof(arr[0]);
 
  // Function call to count the number
  // of pairs whose XOR is even
  printf("%d\n", countPairs(arr, N));
 
  return 0;
}
 
// This code is contributed by phalashi.

// Java program to implement the above approach
public class GFG
{
 
  // Function to maximize the count
  // of pairs with even XOR possible
  // in an array by given operations
  static int countPairs(int []arr, int N)
  {
 
    // Stores count of odd
    // array elements
    int odd = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
      // If arr[i] is odd
      if ((arr[i] & 1)!=0)
        odd++;
    }
 
    // Stores the total number
    // of even pairs
    int ans = (N - odd + odd / 2
               - 1)
      + odd / 2;
 
    return ans;
  }
 
  // Driver Code
  public static void main(String args[])
  {
 
    // Input
    int []arr = { 4, 6, 1, 3 };
    int N = arr.length;
 
    // Function call to count the number
    // of pairs whose XOR is even
    System.out.println(countPairs(arr, N));
  }
}
 
// This code is contributed by AnkThon.

# Python3 program to implement the above approach
 
# Function to maximize the count
# of pairs with even XOR possible
# in an array by given operations
def countPairs(arr, N):
   
    # Stores count of odd
    # array elements
    odd = 0
 
    # Traverse the array
    for i in range(N):
 
        # If arr[i] is odd
        if (arr[i] & 1):
            odd += 1
 
    # Stores the total number
    # of even pairs
    ans = (N - odd + odd // 2 - 1) + odd // 2
 
    return ans
 
# Driver Code
if __name__ == '__main__':
   
  # Input
    arr =[4, 6, 1, 3]
    N = len(arr)
 
    # Function call to count the number
    # of pairs whose XOR is even
    print (countPairs(arr, N))
 
    # This code is contributed by mohit kumar 29.

// C# program to implement the above approach
using System;
class GFG
{
 
// Function to maximize the count
// of pairs with even XOR possible
// in an array by given operations
static int countPairs(int []arr, int N)
{
   
    // Stores count of odd
    // array elements
    int odd = 0;
 
    // Traverse the array
    for (int i = 0; i < N; i++)
    {
 
        // If arr[i] is odd
        if ((arr[i] & 1)!=0)
            odd++;
    }
 
    // Stores the total number
    // of even pairs
    int ans = (N - odd + odd / 2
               - 1)
              + odd / 2;
 
    return ans;
}
 
// Driver Code
public static void Main()
{
   
    // Input
    int []arr = { 4, 6, 1, 3 };
    int N = arr.Length;
 
    // Function call to count the number
    // of pairs whose XOR is even
    Console.Write(countPairs(arr, N));
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
// JavaScript program to implement the above approach
 
// Function to maximize the count
// of pairs with even XOR possible
// in an array by given operations
function countPairs(arr, N)
{
    // Stores count of odd
    // array elements
    let odd = 0;
 
    // Traverse the array
    for (let i = 0; i < N; i++) {
 
        // If arr[i] is odd
        if (arr[i] & 1)
            odd++;
    }
 
    // Stores the total number
    // of even pairs
    let ans = (N - odd + Math.floor(odd / 2) - 1) + Math.floor(odd / 2);
 
    return ans;
}
 
// Driver Code
 
    // Input
    let arr = [ 4, 6, 1, 3 ];
    let N = arr.length;
 
    // Function call to count the number
    // of pairs whose XOR is even
    document.write(countPairs(arr, N));
 
// This code is contributed by Surbhi Tyagi.
 
</script>

3

Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.

Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.