Encuentre un subarreglo de longitud K que tenga Bitwise XOR igual al de los elementos restantes del arreglo

Dada una array arr[] de tamaño N , la tarea es verificar si existe algún subarreglo de tamaño K en la array o no, cuyo Bitwise XOR es igual al Bitwise XOR de los elementos restantes de la array. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba «NO» .

Ejemplos :

Entrada: arr[] = { 2, 3, 3, 5, 7, 7, 3, 4 }, K = 5 
Salida: SÍ 
Explicación: 
Bitwise XOR del subarreglo { 3, 3, 5, 7, 7 } es igual a 5 
Bitwise XOR de { 2, 3, 4 } es igual a 5. 
Por lo tanto, la salida requerida es SÍ.

Entrada: arr[] = { 2, 3, 4, 5, 6, 7, 4 }, K = 2 
Salida: NO

Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los subarreglos de tamaño K . Para cada subarreglo, verifique si el XOR bit a bit del subarreglo es igual al XOR bit a bit de los elementos restantes o no. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba «NO»

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

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando la técnica de ventana deslizante . Las siguientes son las observaciones:

Si X ^ Y = Z, entonces X ^ Z = Y 
SubarrayXOR = arr[i] ^ arr[i + 1] ^ … ^ arr[j] 
totalXOR = arr[0] ^ arr[1] ^ arr[2] … .. ^ arr[N – 1] 
XOR bit a bit de los elementos restantes de la array = totalXOR ^ SubarrayXOR 
 

  • Calcule el XOR bit a bit de todos los elementos de la array , por ejemplo, totalXOR .
  • Calcule el XOR bit a bit de los primeros K elementos de la array, digamos SubarrayXOR .
  • Utilice la técnica de ventana deslizante , recorra cada subarreglo de tamaño K y verifique si Bitwise XOR del subarreglo es igual a Bitwise XOR de los elementos restantes del arreglo o no. Si se encuentra que es cierto, escriba «SÍ» .
  • De lo contrario, escriba «NO» .

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;
 
// Utility function to check if subarray
// of size K exits whose XOR of elements
// equal to XOR ofremaning array elements
bool isSubarrayExistUtil(int arr[], int K, int N)
{
 
    int totalXOR = 0;
    int SubarrayXOR = 0;
 
    // Find XOR of whole array
    for (int i = 0; i < N; i++)
        totalXOR ^= arr[i];
 
    // Find XOR of first K elements
    for (int i = 0; i < K; i++)
        SubarrayXOR ^= arr[i];
    if (SubarrayXOR == (totalXOR ^ SubarrayXOR))
        return true;
 
    for (int i = K; i < N; i++) {
 
        // Adding XOR of next element
        SubarrayXOR ^= arr[i];
 
        // Removing XOR of previous element
        SubarrayXOR ^= arr[i - 1];
 
        // Check if XOR of current subarray matches
        // with the XOR of remaining elements or not
        if (SubarrayXOR == (totalXOR ^ SubarrayXOR))
            return true;
    }
    return false;
}
 
// Function to check if subarray of size
// K exits whose XOR of elements equal
// to XOR ofremaning array elements
void isSubarrayExist(int arr[], int K, int N)
{
    if (isSubarrayExistUtil(arr, K, N))
        cout << "YES\n";
    else
        cout << "NO\n";
}
 
// Driver Code
int32_t main()
{
    // Given array
    int arr[] = { 2, 3, 3, 5, 7, 7, 3, 4 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given K
    int K = 5;
 
    // Function Call
    isSubarrayExist(arr, K, N);
}

C

// C program to implement
// the above approach
 
#include <stdbool.h> //to use true, false keywords
#include <stdint.h> //to use int_32
#include <stdio.h>
 
// Utility function to check if subarray
// of size K exits whose XOR of elements
// equal to XOR ofremaning array elements
bool isSubarrayExistUtil(int arr[], int K, int N)
{
 
  int totalXOR = 0;
  int SubarrayXOR = 0;
 
  // Find XOR of whole array
  for (int i = 0; i < N; i++)
    totalXOR ^= arr[i];
 
  // Find XOR of first K elements
  for (int i = 0; i < K; i++)
    SubarrayXOR ^= arr[i];
  if (SubarrayXOR == (totalXOR ^ SubarrayXOR))
    return true;
 
  for (int i = K; i < N; i++) {
 
    // Adding XOR of next element
    SubarrayXOR ^= arr[i];
 
    // Removing XOR of previous element
    SubarrayXOR ^= arr[i - 1];
 
    // Check if XOR of current subarray matches
    // with the XOR of remaining elements or not
    if (SubarrayXOR == (totalXOR ^ SubarrayXOR))
      return true;
  }
  return false;
}
 
// Function to check if subarray of size
// K exits whose XOR of elements equal
// to XOR ofremaning array elements
void isSubarrayExist(int arr[], int K, int N)
{
  if (isSubarrayExistUtil(arr, K, N))
    printf("YES\n");
  else
    printf("NO\n");
}
 
// Driver Code
int32_t main()
{
  // Given array
  int arr[] = { 2, 3, 3, 5, 7, 7, 3, 4 };
 
  // Size of the array
  int N = sizeof(arr) / sizeof(arr[0]);
 
  // Given K
  int K = 5;
 
  // Function Call
  isSubarrayExist(arr, K, N);
}
 
// This code is contributed by phalashi.

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Utility function to check if subarray
// of size K exits whose XOR of elements
// equal to XOR ofremaning array elements
static boolean isSubarrayExistUtil(int arr[],
                                   int K, int N)
{
    int totalXOR = 0;
    int SubarrayXOR = 0;
 
    // Find XOR of whole array
    for(int i = 0; i < N; i++)
        totalXOR ^= arr[i];
 
    // Find XOR of first K elements
    for(int i = 0; i < K; i++)
        SubarrayXOR ^= arr[i];
    if (SubarrayXOR == (totalXOR ^ SubarrayXOR))
        return true;
 
    for(int i = K; i < N; i++)
    {
         
        // Adding XOR of next element
        SubarrayXOR ^= arr[i];
 
        // Removing XOR of previous element
        SubarrayXOR ^= arr[i - 1];
 
        // Check if XOR of current subarray matches
        // with the XOR of remaining elements or not
        if (SubarrayXOR == (totalXOR ^ SubarrayXOR))
            return true;
    }
    return false;
}
 
// Function to check if subarray of size
// K exits whose XOR of elements equal
// to XOR ofremaning array elements
static void isSubarrayExist(int arr[],
                            int K, int N)
{
    if (isSubarrayExistUtil(arr, K, N))
        System.out.print("YES\n");
    else
        System.out.print("NO\n");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array
    int arr[] = { 2, 3, 3, 5, 7, 7, 3, 4 };
 
    // Size of the array
    int N = arr.length;
 
    // Given K
    int K = 5;
 
    // Function Call
    isSubarrayExist(arr, K, N);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to implement
# the above approach
 
# Utility function to check if subarray
# of size K exits whose XOR of elements
# equal to XOR ofremaning array elements
def isSubarrayExistUtil(arr, K, N):
    totalXOR = 0
    SubarrayXOR = 0
 
    # Find XOR of whole array
    for i in range(N):
        totalXOR ^= arr[i]
 
    # Find XOR of first K elements
    for i in range(K):
        SubarrayXOR ^= arr[i]
    if (SubarrayXOR == (totalXOR ^ SubarrayXOR)):
        return True
 
    for i in range(K, N):
 
        # Adding XOR of next element
        SubarrayXOR ^= arr[i]
 
        # Removing XOR of previous element
        SubarrayXOR ^= arr[i - 1]
 
        # Check if XOR of current subarray matches
        # with the XOR of remaining elements or not
        if (SubarrayXOR == (totalXOR ^ SubarrayXOR)):
            return True
    return False
 
# Function to check if subarray of size
# K exits whose XOR of elements equal
# to XOR ofremaning array elements
def isSubarrayExist(arr, K, N):
    if (isSubarrayExistUtil(arr, K, N)):
        print("YES")
    else:
        print("NO")
 
# Driver Code
if __name__ == '__main__':
     
    # Given array
    arr = [2, 3, 3, 5, 7, 7, 3, 4]
 
    # Size of the array
    N = len(arr)
 
    # Given K
    K = 5
 
    # Function Call
    isSubarrayExist(arr, K, N)
 
    # This code is contributed by mohit kumar 29

C#

// C# program to implement
// the above approach
using System;
class GFG
{
 
// Utility function to check if subarray
// of size K exits whose XOR of elements
// equal to XOR ofremaning array elements
static bool isSubarrayExistUtil(int []arr,
                                   int K, int N)
{
    int totalXOR = 0;
    int SubarrayXOR = 0;
 
    // Find XOR of whole array
    for(int i = 0; i < N; i++)
        totalXOR ^= arr[i];
 
    // Find XOR of first K elements
    for(int i = 0; i < K; i++)
        SubarrayXOR ^= arr[i];
    if (SubarrayXOR == (totalXOR ^ SubarrayXOR))
        return true;
    for(int i = K; i < N; i++)
    {
         
        // Adding XOR of next element
        SubarrayXOR ^= arr[i];
 
        // Removing XOR of previous element
        SubarrayXOR ^= arr[i - 1];
 
        // Check if XOR of current subarray matches
        // with the XOR of remaining elements or not
        if (SubarrayXOR == (totalXOR ^ SubarrayXOR))
            return true;
    }
    return false;
}
 
// Function to check if subarray of size
// K exits whose XOR of elements equal
// to XOR ofremaning array elements
static void isSubarrayExist(int []arr,
                            int K, int N)
{
    if (isSubarrayExistUtil(arr, K, N))
        Console.Write("YES\n");
    else
        Console.Write("NO\n");
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array
    int []arr = { 2, 3, 3, 5, 7, 7, 3, 4 };
 
    // Size of the array
    int N = arr.Length;
 
    // Given K
    int K = 5;
 
    // Function Call
    isSubarrayExist(arr, K, N);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// javascript program to implement
// the above approach
 
    // Utility function to check if subarray
    // of size K exits whose XOR of elements
    // equal to XOR ofremaning array elements
    function isSubarrayExistUtil(arr , K , N)
    {
        var totalXOR = 0;
        var SubarrayXOR = 0;
 
        // Find XOR of whole array
        for (i = 0; i < N; i++)
            totalXOR ^= arr[i];
 
        // Find XOR of first K elements
        for (i = 0; i < K; i++)
            SubarrayXOR ^= arr[i];
        if (SubarrayXOR == (totalXOR ^ SubarrayXOR))
            return true;
 
        for (i = K; i < N; i++) {
 
            // Adding XOR of next element
            SubarrayXOR ^= arr[i];
 
            // Removing XOR of previous element
            SubarrayXOR ^= arr[i - 1];
 
            // Check if XOR of current
            // subarray matches
            // with the XOR of remaining
            // elements or not
            if (SubarrayXOR ==
            (totalXOR ^ SubarrayXOR))
                return true;
        }
        return false;
    }
 
    // Function to check if subarray of size
    // K exits whose XOR of elements equal
    // to XOR ofremaning array elements
    function isSubarrayExist(arr , K , N) {
        if (isSubarrayExistUtil(arr, K, N))
            document.write("YES\n");
        else
            document.write("NO\n");
    }
 
    // Driver Code
     
 
        // Given array
        var arr = [ 2, 3, 3, 5, 7, 7, 3, 4 ];
 
        // Size of the array
        var N = arr.length;
 
        // Given K
        var K = 5;
 
        // Function Call
        isSubarrayExist(arr, K, N);
 
// This code contributed by Rajput-Ji
 
</script>
Producción: 

YES

 

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

Publicación traducida automáticamente

Artículo escrito por Stream_Cipher 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 *