Dada una array arr[] y un entero K , la tarea es encontrar la suma XOR bit a bit mínima de cualquier subarreglo de tamaño K en la array dada.
Ejemplos:
Entrada: arr[] = {3, 7, 90, 20, 10, 50, 40}, K = 3 Salida: 16
Explicación :
El
subarreglo {10, 50, 40} tiene el XOR mínimo
Entrada: arr[] = { 3, 7, 5, 20, -10, 0, 12}, K = 2
Salida: 17
Explicación:
El subarreglo {5, 20} tiene el XOR mínimo
Enfoque ingenuo: una solución simple es considerar cada elemento como el comienzo del subarreglo de tamaño k y calcular XOR del subarreglo que comienza con este elemento.
Complejidad de tiempo: O(N * K)
Enfoque eficiente: La idea es utilizar la técnica de ventana deslizante de tamaño K y realizar un seguimiento de la suma XOR de los elementos K actuales . Para calcular el XOR de la ventana actual, realice XOR con el primer elemento de la ventana anterior para descartar ese elemento y con el elemento actual para agregar este elemento a la ventana. De manera similar, deslice las ventanas para encontrar el XOR mínimo del subarreglo de tamaño K .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// subarray with minimum XOR
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum
// XOR of the subarray of size K
void findMinXORSubarray(int arr[],
int n, int k)
{
// K must be smaller
// than or equal to n
if (n < k)
return;
// Initialize beginning
// index of result
int res_index = 0;
// Compute XOR sum of first
// subarray of size K
int curr_xor = 0;
for (int i = 0; i < k; i++)
curr_xor ^= arr[i];
// Initialize minimum XOR
// sum as current xor
int min_xor = curr_xor;
// Traverse from (k+1)'th
// element to n'th element
for (int i = k; i < n; i++) {
// XOR with current item
// and first item of
// previous subarray
curr_xor ^= (arr[i] ^ arr[i - k]);
// Update result if needed
if (curr_xor < min_xor) {
min_xor = curr_xor;
res_index = (i - k + 1);
}
}
cout << min_xor << "\n";
}
// Driver Code
int main()
{
int arr[] = { 3, 7, 90, 20, 10, 50, 40 };
int k = 3; // Subarray size
int n = sizeof arr / sizeof arr[0];
// Function Call
findMinXORSubarray(arr, n, k);
return 0;
}
Java
// Java implementation to find the
// subarray with minimum XOR
class GFG{
// Function to find the minimum
// XOR of the subarray of size K
static void findMinXORSubarray(int arr[],
int n, int k)
{
// K must be smaller
// than or equal to n
if (n < k)
return;
// Initialize beginning
// index of result
int res_index = 0;
// Compute XOR sum of first
// subarray of size K
int curr_xor = 0;
for(int i = 0; i < k; i++)
curr_xor ^= arr[i];
// Initialize minimum XOR
// sum as current xor
int min_xor = curr_xor;
// Traverse from (k+1)'th
// element to n'th element
for(int i = k; i < n; i++)
{
// XOR with current item
// and first item of
// previous subarray
curr_xor ^= (arr[i] ^ arr[i - k]);
// Update result if needed
if (curr_xor < min_xor)
{
min_xor = curr_xor;
res_index = (i - k + 1);
}
}
System.out.print(min_xor + "\n");
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 7, 90, 20, 10, 50, 40 };
// Subarray size
int k = 3;
int n = arr.length;
// Function Call
findMinXORSubarray(arr, n, k);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 implementation to find the # subarray with minimum XOR # Function to find the minimum # XOR of the subarray of size K def findMinXORSubarray(arr, n, k): # K must be smaller # than or equal to n if (n < k): return # Initialize beginning # index of result res_index = 0 # Compute XOR sum of first # subarray of size K curr_xor = 0 for i in range(0, k): curr_xor = curr_xor ^ arr[i] # Initialize minimum XOR # sum as current xor min_xor = curr_xor # Traverse from (k+1)'th # element to n'th element for i in range(k, n): # XOR with current item # and first item of # previous subarray curr_xor ^= (arr[i] ^ arr[i - k]) # Update result if needed if (curr_xor < min_xor): min_xor = curr_xor res_index = (i - k + 1) print(min_xor, end = '\n') # Driver Code arr = [ 3, 7, 90, 20, 10, 50, 40 ] # Subarray size k = 3 n = len(arr) # Function Call findMinXORSubarray(arr, n, k) # This code is contributed by PratikBasu
C#
// C# implementation to find the
// subarray with minimum XOR
using System;
class GFG{
// Function to find the minimum
// XOR of the subarray of size K
static void findMinXORSubarray(int []arr,
int n, int k)
{
// K must be smaller
// than or equal to n
if (n < k)
return;
// Initialize beginning
// index of result
int res_index = 0;
// Compute XOR sum of first
// subarray of size K
int curr_xor = 0;
for(int i = 0; i < k; i++)
curr_xor ^= arr[i];
// Initialize minimum XOR
// sum as current xor
int min_xor = curr_xor;
// Traverse from (k+1)'th
// element to n'th element
for(int i = k; i < n; i++)
{
// XOR with current item
// and first item of
// previous subarray
curr_xor ^= (arr[i] ^ arr[i - k]);
// Update result if needed
if (curr_xor < min_xor)
{
min_xor = curr_xor;
res_index = (i - k + 1);
}
}
Console.Write(min_xor + "\n");
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 3, 7, 90, 20, 10, 50, 40 };
// Subarray size
int k = 3;
int n = arr.Length;
// Function Call
findMinXORSubarray(arr, n, k);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript implementation to find the
// subarray with minimum XOR
// Function to find the minimum
// XOR of the subarray of size K
function findMinXORSubarray(arr, n, k)
{
// K must be smaller
// than or equal to n
if (n < k)
return;
// Initialize beginning
// index of result
let res_index = 0;
// Compute XOR sum of first
// subarray of size K
let curr_xor = 0;
for (let i = 0; i < k; i++)
curr_xor ^= arr[i];
// Initialize minimum XOR
// sum as current xor
let min_xor = curr_xor;
// Traverse from (k+1)'th
// element to n'th element
for (let i = k; i < n; i++) {
// XOR with current item
// and first item of
// previous subarray
curr_xor ^= (arr[i] ^ arr[i - k]);
// Update result if needed
if (curr_xor < min_xor) {
min_xor = curr_xor;
res_index = (i - k + 1);
}
}
document.write(min_xor + "<br>");
}
// Driver Code
let arr = [ 3, 7, 90, 20, 10, 50, 40 ];
let k = 3; // Subarray size
let n = arr.length;
// Function Call
findMinXORSubarray(arr, n, k);
</script>
16
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA