Dada una array arr[] de tamaño N y un número entero K , la tarea es encontrar la longitud de la subarreglo más larga que tenga Bitwise XOR de todos sus elementos igual a K .
Ejemplos:
Entrada: arr[] = { 1, 2, 4, 7, 2 }, K = 1
Salida: 3
Explicación:
el subarreglo que tiene XOR bit a bit igual a K(= 1) son { { 1 }, { 2, 4, 7 } , { 1 } }.
Por lo tanto, la longitud del subarreglo más largo que tiene XOR bit a bit igual a K(= 1) es 3Entrada: arr[] = { 2, 5, 6, 1, 0, 3, 5, 6 }, K = 4
Salida: 6
Explicación:
el subarreglo que tiene XOR bit a bit igual a K(= 4) are { { 6, 1, 0, 3 }, { 5, 6, 1, 0, 3, 5 } }.
Por lo tanto, la longitud del subarreglo más largo que tiene XOR bit a bit igual a K(= 4) es 6.
Enfoque: el problema se puede resolver utilizando la técnica Hashing y Prefix Sum . Las siguientes son las observaciones:
un 1 ^ un 2 ^ un 3 ^ ….. ^ un norte = K
=> un 2 ^ un 3 ^ ….. ^ un norte ^ K = un 1
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos prefixXOR , para almacenar el XOR bit a bit de todos los elementos hasta el i- ésimo índice de la array dada.
- Inicialice un Map , digamos mp , para almacenar los índices de los XOR de prefijo calculados de la array.
- Inicialice una variable, digamos maxLen , para almacenar la longitud del subarreglo más largo cuyo Bitwise XOR sea igual a K .
- Recorra la array arr[] usando la variable i . Para cada i- ésimo índice, actualice prefixXOR = prefixXOR ^ arr[i] y verifique si (prefixXOR ^ K) está presente en el Mapa o no. Si se determina que es cierto, actualice maxLen = max(maxLen, i – mp[prefixXOR ^ K]) .
- Si prefixXOR no está presente en el mapa, inserte prefixXOR en el mapa.
- Finalmente, imprima el valor de maxLen .
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 find the length of the longest
// subarray whose bitwise XOR is equal to K
int LongestLenXORK(int arr[], int N, int K)
{
// Stores prefix XOR
// of the array
int prefixXOR = 0;
// Stores length of longest subarray
// having bitwise XOR equal to K
int maxLen = 0;
// Stores index of prefix
// XOR of the array
map<int, int> mp;
// Insert 0 into the map
mp[0] = -1;
// Traverse the array
for (int i = 0; i < N; i++) {
// Update prefixXOR
prefixXOR ^= arr[i];
// If (prefixXOR ^ K) present
// in the map
if (mp.count(prefixXOR ^ K)) {
// Update maxLen
maxLen = max(maxLen,
(i - mp[prefixXOR ^ K]));
}
// If prefixXOR not present
// in the Map
if (!mp.count(prefixXOR)) {
// Insert prefixXOR
// into the map
mp[prefixXOR] = i;
}
}
return maxLen;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 4, 7, 2 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 1;
cout<< LongestLenXORK(arr, N, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the length of the longest
// subarray whose bitwise XOR is equal to K
static int LongestLenXORK(int arr[],
int N, int K)
{
// Stores prefix XOR
// of the array
int prefixXOR = 0;
// Stores length of longest subarray
// having bitwise XOR equal to K
int maxLen = 0;
// Stores index of prefix
// XOR of the array
HashMap<Integer,
Integer> mp = new HashMap<Integer,
Integer>();
// Insert 0 into the map
mp.put(0, -1);
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update prefixXOR
prefixXOR ^= arr[i];
// If (prefixXOR ^ K) present
// in the map
if (mp.containsKey(prefixXOR ^ K))
{
// Update maxLen
maxLen = Math.max(maxLen,
(i - mp.get(prefixXOR ^ K)));
}
// If prefixXOR not present
// in the Map
if (!mp.containsKey(prefixXOR))
{
// Insert prefixXOR
// into the map
mp.put(prefixXOR, i);
}
}
return maxLen;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 4, 7, 2 };
int N = arr.length;
int K = 1;
System.out.print(LongestLenXORK(arr, N, K));
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to implement
# the above approach
# Function to find the length of the longest
# subarray whose bitwise XOR is equal to K
def LongestLenXORK(arr, N, K):
# Stores prefix XOR
# of the array
prefixXOR = 0
# Stores length of longest subarray
# having bitwise XOR equal to K
maxLen = 0
# Stores index of prefix
# XOR of the array
mp = {}
# Insert 0 into the map
mp[0] = -1
# Traverse the array
for i in range(N):
# Update prefixXOR
prefixXOR ^= arr[i]
# If (prefixXOR ^ K) present
# in the map
if (prefixXOR ^ K) in mp:
# Update maxLen
maxLen = max(maxLen,
(i - mp[prefixXOR ^ K]))
# If prefixXOR not present
# in the Map
else:
# Insert prefixXOR
# into the map
mp[prefixXOR] = i
return maxLen
# Driver Code
if __name__ == "__main__" :
arr = [ 1, 2, 4, 7, 2 ]
N = len(arr)
K = 1
print(LongestLenXORK(arr, N, K))
# This code is contributed by AnkThon
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the length of the longest
// subarray whose bitwise XOR is equal to K
static int longestLenXORK(int []arr,
int N, int K)
{
// Stores prefix XOR
// of the array
int prefixXOR = 0;
// Stores length of longest subarray
// having bitwise XOR equal to K
int maxLen = 0;
// Stores index of prefix
// XOR of the array
Dictionary<int,
int> mp = new Dictionary<int,
int>();
// Insert 0 into the map
mp.Add(0, -1);
// Traverse the array
for(int i = 0; i < N; i++)
{
// Update prefixXOR
prefixXOR ^= arr[i];
// If (prefixXOR ^ K) present
// in the map
if (mp.ContainsKey(prefixXOR ^ K))
{
// Update maxLen
maxLen = Math.Max(maxLen,
(i - mp[prefixXOR ^ K]));
}
// If prefixXOR not present
// in the Map
if (!mp.ContainsKey(prefixXOR))
{
// Insert prefixXOR
// into the map
mp.Add(prefixXOR, i);
}
}
return maxLen;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {1, 2, 4, 7, 2};
int N = arr.Length;
int K = 1;
Console.Write(longestLenXORK(arr, N, K));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the length of the longest
// subarray whose bitwise XOR is equal to K
function LongestLenXORK(arr, N, K)
{
// Stores prefix XOR
// of the array
var prefixXOR = 0;
// Stores length of longest subarray
// having bitwise XOR equal to K
var maxLen = 0;
// Stores index of prefix
// XOR of the array
var mp = new Map();
// Insert 0 into the map
mp.set(0, -1);
// Traverse the array
for (var i = 0; i < N; i++) {
// Update prefixXOR
prefixXOR ^= arr[i];
// If (prefixXOR ^ K) present
// in the map
if (mp.has(prefixXOR ^ K)) {
// Update maxLen
maxLen = Math.max(maxLen,
(i - mp.get(prefixXOR ^ K)));
}
// If prefixXOR not present
// in the Map
if (!mp.has(prefixXOR)) {
// Insert prefixXOR
// into the map
mp.set(prefixXOR, i);
}
}
return maxLen;
}
// Driver Code
var arr = [1, 2, 4, 7, 2];
var N = arr.length;
var K = 1;
document.write( LongestLenXORK(arr, N, K));
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por papansarkar101 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA