Cuente las formas de hacer que Bitwise XOR de elementos indexados pares e impares sea igual eliminando un elemento de array

Dada una array arr[] de longitud N , la tarea es encontrar el recuento de los índices de la array, de modo que al eliminar un elemento de estos índices, la xor bit a bit de los elementos indexados impares y los elementos indexados pares (indexación basada en 1) sean iguales. .

Ejemplos:

Entrada: arr[] = {1, 0, 1, 0, 1}, N = 5
Salida: 3
Explicación: 

  1. Eliminar un elemento del índice 3 modifica arr[] a {1, 0, 0, 1}. Por lo tanto, xor de elementos indexados pares e impares es 0.
  2. Eliminar un elemento del índice 1 modifica arr[] a {0, 1, 0, 1}. Por lo tanto, xor de elementos indexados pares e impares es 0.
  3. Eliminar un elemento del índice 5 modifica arr[] a {1, 0, 1, 0}. Por lo tanto, xor de elementos indexados pares e impares es 0.

Entrada: arr[] = {1, 0, 0, 0, 1}, N=5
Salida:

  1. Eliminar un elemento del índice 3 modifica arr[] a {1, 0, 0, 1}. Por lo tanto, xor de elementos indexados pares e impares es 0.
  2. Eliminar un elemento del índice 2 modifica arr[] a {1, 0, 0, 1}. Por lo tanto, xor de elementos indexados pares e impares es 1.
  3. Eliminar un elemento del índice 4 modifica arr[] a {1, 0, 0, 0}. Por lo tanto, xor de elementos indexados pares e impares es 1.
 

Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y, para cada elemento de la array, verificar si eliminar el elemento de la array hace que el XOR bit a bit de los elementos de la array indexados pares e impares sea igual o no. Si se encuentra que es cierto, entonces incremente el conteo. Finalmente, imprima el conteo. 

Complejidad de Tiempo: O(N 2
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar en función de la observación de que la eliminación de cualquier elemento de la array dada hace que los índices pares de los elementos sucesivos sean impares y los índices impares de los elementos sucesivos sean pares. Siga los pasos a continuación para resolver el problema:

  1. Inicialice las variables curr_odd, curr_even, post_odd, post_even y res con 0 .
  2. Atraviese la array en sentido inverso y realice lo siguiente: 
    • Si el elemento actual es impar, XOR con post_odd .
    • De lo contrario, XOR elemento actual con post_even .
  3. Ahora, recorra la array dada y realice lo siguiente: 
    • Si el índice actual es impar, elimine el elemento actual de post_odd actualizando post_odd con Bitwise XOR de post_odd y el elemento actual.
    • De lo contrario, elimine el elemento actual de post_even de manera similar.
    • Inicialice las variables X e Y .
    • Asigne XOR de curr_odd y post_even en X . Por lo tanto, X almacena xor de todos los elementos indexados impares.
    • Asigne xor de curr_even y post_odd en Y . Por lo tanto, Y almacena xor de todos los elementos indexados pares.
    • Comprueba si X es igual a Y. Si se determina que es cierto, incremente res en 1 .
    • Si el índice actual es impar, entonces XOR elemento actual con curr_odd .
    • De lo contrario, XOR elemento actual con curr_even .
  4. Finalmente, imprima el res .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count ways to make Bitwise
// XOR of odd and even indexed elements
// equal by removing an array element
void Remove_one_element(int arr[], int n)
{
    // Stores xor of odd and even
    // indexed elements from the end
    int post_odd = 0, post_even = 0;
 
    // Stores xor of odd and even
    // indexed elements from the start
    int curr_odd = 0, curr_even = 0;
 
    // Stores the required count
    int res = 0;
 
    // Traverse the array in reverse
    for (int i = n - 1; i >= 0; i--) {
 
        // If i is odd
        if (i % 2)
            post_odd ^= arr[i];
 
        // If i is even
        else
            post_even ^= arr[i];
    }
 
    // Traverse the array
    for (int i = 0; i < n; i++) {
 
        // If i is odd
        if (i % 2)
            post_odd ^= arr[i];
 
        // If i is even
        else
            post_even ^= arr[i];
 
        // Removing arr[i], post_even stores
        // XOR of odd indexed elements
        int X = curr_odd ^ post_even;
 
        // Removing arr[i], post_odd stores
        // XOR of even indexed elements
        int Y = curr_even ^ post_odd;
 
        // Check if they are equal
        if (X == Y)
            res++;
 
        // If i is odd, xor it
        // with curr_odd
        if (i % 2)
            curr_odd ^= arr[i];
 
        // If i is even, xor it
        // with curr_even
        else
            curr_even ^= arr[i];
    }
 
    // Finally print res
    cout << res << endl;
}
 
// Drivers Code
int main()
{
 
    // Given array
    int arr[] = { 1, 0, 1, 0, 1 };
 
    // Given size
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    Remove_one_element(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
class GFG {
     
    // Function to count ways to make Bitwise
    // XOR of odd and even indexed elements
    // equal by removing an array element
    static void Remove_one_element(int arr[], int n)
    {
        // Stores xor of odd and even
        // indexed elements from the end
        int post_odd = 0, post_even = 0;
     
        // Stores xor of odd and even
        // indexed elements from the start
        int curr_odd = 0, curr_even = 0;
     
        // Stores the required count
        int res = 0;
     
        // Traverse the array in reverse
        for (int i = n - 1; i >= 0; i--)
        {
     
            // If i is odd
            if (i % 2 != 0)
                post_odd ^= arr[i];
     
            // If i is even
            else
                post_even ^= arr[i];
        }
     
        // Traverse the array
        for (int i = 0; i < n; i++)
        {
     
            // If i is odd
            if (i % 2 != 0)
                post_odd ^= arr[i];
     
            // If i is even
            else
                post_even ^= arr[i];
     
            // Removing arr[i], post_even stores
            // XOR of odd indexed elements
            int X = curr_odd ^ post_even;
     
            // Removing arr[i], post_odd stores
            // XOR of even indexed elements
            int Y = curr_even ^ post_odd;
     
            // Check if they are equal
            if (X == Y)
                res++;
     
            // If i is odd, xor it
            // with curr_odd
            if (i % 2 != 0)
                curr_odd ^= arr[i];
     
            // If i is even, xor it
            // with curr_even
            else
                curr_even ^= arr[i];
        }
     
        // Finally print res
        System.out.println(res);
    }
     
    // Drivers Code
    public static void main (String[] args)
    {
     
        // Given array
        int arr[] = { 1, 0, 1, 0, 1 };
     
        // Given size
        int N = arr.length;
     
        // Function call
        Remove_one_element(arr, N);   
    }
 
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 program for the above approach
 
# Function to count ways to make Bitwise
# XOR of odd and even indexed elements
# equal by removing an array element
def Remove_one_element(arr, n):
 
    # Stores xor of odd and even
    # indexed elements from the end
    post_odd = 0
    post_even = 0
 
    # Stores xor of odd and even
    # indexed elements from the start
    curr_odd = 0
    curr_even = 0
 
    # Stores the required count
    res = 0
 
    # Traverse the array in reverse
    for i in range(n - 1, -1, -1):
 
        # If i is odd
        if (i % 2):
            post_odd ^= arr[i]
 
        # If i is even
        else:
            post_even ^= arr[i]
 
    # Traverse the array
    for i in range(n):
 
        # If i is odd
        if (i % 2):
            post_odd ^= arr[i]
 
        # If i is even
        else:
            post_even ^= arr[i]
 
        # Removing arr[i], post_even stores
        # XOR of odd indexed elements
        X = curr_odd ^ post_even
 
        # Removing arr[i], post_odd stores
        # XOR of even indexed elements
        Y = curr_even ^ post_odd
 
        # Check if they are equal
        if (X == Y):
            res += 1
 
        # If i is odd, xor it
        # with curr_odd
        if (i % 2):
            curr_odd ^= arr[i]
 
        # If i is even, xor it
        # with curr_even
        else:
            curr_even ^= arr[i]
 
    # Finally print res
    print(res)
 
# Drivers Code
if __name__ == "__main__" :
 
    # Given array
    arr = [ 1, 0, 1, 0, 1 ]
 
    # Given size
    N = len(arr)
 
    # Function call
    Remove_one_element(arr, N)
 
# This code is contributed by AnkitRai01

C#

// C# program to implement
// the above approach 
using System;
 
class GFG {
      
    // Function to count ways to make Bitwise
    // XOR of odd and even indexed elements
    // equal by removing an array element
    static void Remove_one_element(int[] arr, int n)
    {
        // Stores xor of odd and even
        // indexed elements from the end
        int post_odd = 0, post_even = 0;
      
        // Stores xor of odd and even
        // indexed elements from the start
        int curr_odd = 0, curr_even = 0;
      
        // Stores the required count
        int res = 0;
      
        // Traverse the array in reverse
        for (int i = n - 1; i >= 0; i--)
        {
      
            // If i is odd
            if (i % 2 != 0)
                post_odd ^= arr[i];
      
            // If i is even
            else
                post_even ^= arr[i];
        }
      
        // Traverse the array
        for (int i = 0; i < n; i++)
        {
      
            // If i is odd
            if (i % 2 != 0)
                post_odd ^= arr[i];
      
            // If i is even
            else
                post_even ^= arr[i];
      
            // Removing arr[i], post_even stores
            // XOR of odd indexed elements
            int X = curr_odd ^ post_even;
      
            // Removing arr[i], post_odd stores
            // XOR of even indexed elements
            int Y = curr_even ^ post_odd;
      
            // Check if they are equal
            if (X == Y)
                res++;
      
            // If i is odd, xor it
            // with curr_odd
            if (i % 2 != 0)
                curr_odd ^= arr[i];
      
            // If i is even, xor it
            // with curr_even
            else
                curr_even ^= arr[i];
        }
      
        // Finally print res
        Console.WriteLine(res);
    }
      
    // Drivers Code
    public static void Main ()
    {
      
        // Given array
        int[] arr = { 1, 0, 1, 0, 1 };
      
        // Given size
        int N = arr.Length;
      
        // Function call
        Remove_one_element(arr, N);   
    }
  
}
 
// This code is contributed by susmitakundugoaldanga

Javascript

<script>
// JavaScript program to implement
// the above approach
 
    // Function to count ways to make Bitwise
    // XOR of odd and even indexed elements
    // equal by removing an array element
    function Remove_one_element(arr, n)
    {
        // Stores xor of odd and even
        // indexed elements from the end
        let post_odd = 0, post_even = 0;
      
        // Stores xor of odd and even
        // indexed elements from the start
        let curr_odd = 0, curr_even = 0;
      
        // Stores the required count
        let res = 0;
      
        // Traverse the array in reverse
        for (let i = n - 1; i >= 0; i--)
        {
      
            // If i is odd
            if (i % 2 != 0)
                post_odd ^= arr[i];
      
            // If i is even
            else
                post_even ^= arr[i];
        }
      
        // Traverse the array
        for (let i = 0; i < n; i++)
        {
      
            // If i is odd
            if (i % 2 != 0)
                post_odd ^= arr[i];
      
            // If i is even
            else
                post_even ^= arr[i];
      
            // Removing arr[i], post_even stores
            // XOR of odd indexed elements
            let X = curr_odd ^ post_even;
      
            // Removing arr[i], post_odd stores
            // XOR of even indexed elements
            let Y = curr_even ^ post_odd;
      
            // Check if they are equal
            if (X == Y)
                res++;
      
            // If i is odd, xor it
            // with curr_odd
            if (i % 2 != 0)
                curr_odd ^= arr[i];
      
            // If i is even, xor it
            // with curr_even
            else
                curr_even ^= arr[i];
        }
      
        // Finally print res
        document.write(res);
    }
  
 
// Driver Code
 
    // Given array
        let arr = [ 1, 0, 1, 0, 1 ];
      
        // Given size
        let N = arr.length;
      
        // Function call
        Remove_one_element(arr, N);
     
</script>
Producción: 

3

 

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

Publicación traducida automáticamente

Artículo escrito por saikumarkudikala y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *