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