Dado un arreglo de enteros, la tarea es encontrar el valor XOR máximo de un subarreglo de tamaño K.
Ejemplos:
Input : arr[] = {2, 5, 8 ,1 , 1 ,3} k = 3
Output : 15
Explanation : All subarrays of size k (=3) and
their XOR values are:
{2, 5, 8} => XOR value = 15
{5, 8, 1} => XOR value = 12
{8, 1, 1} => XOR value = 8
{1, 1, 3} => XOR value = 3
Maximum of all XOR values = 15
Input : arr[] = {1, 2, 4, 5, 6}
Output : 6
Una solución simple es considerar todos los subarreglos de tamaño k uno por uno y calcular el valor XOR. Finalmente devuelve el máximo de todos los valores XOR. Esta solución toma tiempo O(n*k).
Una solución eficiente toma O(n) tiempo. La idea es simple, podemos encontrar el valor XOR del subarreglo actual de tamaño k eliminando el primer elemento del subarreglo anterior y agregando el último elemento del subarreglo actual. Podemos eliminar un elemento del XOR actual haciendo XOR nuevamente debido a la propiedad de XOR de que a ^ x ^ x = a.
Algoritmo:
Let input array be 'arr[]' and size of array be 'n'
max_xor ; // user to store maximum xor value
current_xor; // user to store xor value of current subarray
// of size k
// First compute xor value of first subarray of size k
// (i goes from 0 to k)
corrent_xor = current_xor ^ arr[i]
// Initialize maximum XOR
max_xor = current_xor
Traversal rest array (i goes from k to n-1 )
a). remove first element of previous subarray
current_xor = current_xor ^ arr[i-k]
b). add new element to subarray
current_xor = current_xor ^ arr[i]
c). update max_xor = max(max_xor, current_xor)
return max_xor
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++/C program to find maximum xor value of subarray of
// size k
#include<iostream>
using namespace std;
// Returns maximum XOR value of subarray of size k
int maximumXOR(int arr[] , int n , int k)
{
// Compute XOR value of first subarray of size k
int current_xor = 0 ;
for (int i = 0 ; i < k ; i++)
current_xor = current_xor ^ arr[i];
// Traverse rest of the array
int max_xor = current_xor;
for (int i = k ; i < n; i++)
{
// First remove previous subarray's first
// element
current_xor = current_xor ^ arr[i-k];
// add new element
current_xor = current_xor ^ arr[i];
// Update maximum xor value
max_xor = max(max_xor, current_xor);
}
return max_xor;
}
// Driver program
int main()
{
int arr[] = {2, 5, 8 ,1 , 1 ,3} ;
int k = 3;
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Maximum XOR : " << maximumXOR(arr, n, k);
return 0;
}
Java
// Java program to find maximum xor value of
// subarray of size k
import java.io.*;
class GFG {
// Returns maximum XOR value of subarray of size k
static int maximumXOR(int arr[] , int n , int k)
{
// Compute XOR value of first subarray of size k
int current_xor = 0 ;
for (int i = 0 ; i < k ; i++)
current_xor = current_xor ^ arr[i];
// Traverse rest of the array
int max_xor = current_xor;
for (int i = k ; i < n; i++)
{
// First remove previous subarray's first
// element
current_xor = current_xor ^ arr[i-k];
// add new element
current_xor = current_xor ^ arr[i];
// Update maximum xor value
max_xor = Math.max(max_xor, current_xor);
}
return max_xor;
}
// Driver program
public static void main (String[] args)
{
int arr[] = {2, 5, 8 ,1 , 1 ,3} ;
int k = 3;
int n = arr.length;
System.out.println( "Maximum XOR : "
+ maximumXOR(arr, n, k));
}
}
// This code is contributed by anuj_67.
Python 3
# Python3 program to find maximum
# xor value of subarray of
# size
# Returns maximum XOR value
# of subarray of size k
def maximumXOR(arr , n , k):
# Compute XOR value of first
# subarray of size k
current_xor = 0
for i in range ( k):
current_xor = current_xor ^ arr[i]
# Traverse rest of the array
max_xor = current_xor
for i in range( k,n):
# First remove previous subarray's first
# element
current_xor = current_xor ^ arr[i-k]
# add new element
current_xor = current_xor ^ arr[i]
# Update maximum xor value
max_xor = max(max_xor, current_xor)
return max_xor
# Driver program
if __name__ =="__main__":
arr = [2, 5, 8 ,1 , 1 ,3]
k = 3
n = len(arr)
print ("Maximum XOR : "
,maximumXOR(arr, n, k))
# This code is contributed by
# ChitraNayal
C#
// C# program to find maximum
// xor value of subarray of
// size k
using System;
class GFG {
// Returns maximum XOR value
// of subarray of size k
static int maximumXOR(int []arr,
int n, int k)
{
// Compute XOR value of first
// subarray of size k
int current_xor = 0 ;
for (int i = 0; i < k; i++)
current_xor = current_xor ^ arr[i];
// Traverse rest of the array
int max_xor = current_xor;
for (int i = k ; i < n; i++)
{
// First remove previous
// subarray's first
// element
current_xor = current_xor ^ arr[i-k];
// add new element
current_xor = current_xor ^ arr[i];
// Update maximum xor value
max_xor = Math.Max(max_xor, current_xor);
}
return max_xor;
}
// Driver Code
public static void Main ()
{
int []arr = {2, 5, 8 ,1 , 1 ,3} ;
int k = 3;
int n = arr.Length;
Console.WriteLine("Maximum XOR : "
+ maximumXOR(arr, n, k));
}
}
// This code is contributed by anuj_67.
PHP
<?php
// PHP program to find maximum
// xor value of subarray of size k
// Returns maximum XOR value
// of subarray of size k
function maximumXOR($arr, $n, $k)
{
// Compute XOR value of
// first subarray of size k
$current_xor = 0 ;
for ($i = 0 ; $i < $k ; $i++)
$current_xor = $current_xor ^
$arr[$i];
// Traverse rest of the array
$max_xor = $current_xor;
for ($i = $k ; $i < $n; $i++)
{
// First remove previous
// subarray's first element
$current_xor = $current_xor ^
$arr[$i - $k];
// add new element
$current_xor = $current_xor ^
$arr[$i];
// Update maximum xor value
$max_xor = max($max_xor,
$current_xor);
}
return $max_xor;
}
// Driver Code
$arr = array(2, 5, 8, 1, 1, 3) ;
$k = 3;
$n = sizeof($arr);
echo "Maximum XOR : ",
maximumXOR($arr, $n, $k);
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript program to find maximum xor value of
// subarray of size k
// Returns maximum XOR value of subarray of size k
function maximumXOR(arr,n,k)
{
// Compute XOR value of first subarray of size k
let current_xor = 0 ;
for (let i = 0 ; i < k ; i++)
current_xor = current_xor ^ arr[i];
// Traverse rest of the array
let max_xor = current_xor;
for (let i = k ; i < n; i++)
{
// First remove previous subarray's first
// element
current_xor = current_xor ^ arr[i-k];
// add new element
current_xor = current_xor ^ arr[i];
// Update maximum xor value
max_xor = Math.max(max_xor, current_xor);
}
return max_xor;
}
// Driver program
let arr=[2, 5, 8 ,1 , 1 ,3];
let k = 3;
let n = arr.length;
document.write( "Maximum XOR : "
+ maximumXOR(arr, n, k));
// This code is contributed by rag2127
</script>
Producción
Maximum XOR : 15
Complejidad de tiempo : O(n)
Este artículo es una contribución de Nishant_Singh (Pintu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA