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 3 ), ya que tenemos que usar bucles anidados para atravesar N 3 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:
- Atraviesa la array .
- Cuenta la frecuencia de los números impares y guárdala en una variable, digamos impar .
- 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) .
- 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).
- 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++
// 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
// 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
// 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
# 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#
// 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.
Javascript
<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.
Publicación traducida automáticamente
Artículo escrito por subhammahato348 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA