Dada una array de longitud n (n > k), tenemos que encontrar la suma de xor de todos los elementos de las sub-arrays que son de longitud k.
Ejemplos:
Entrada: arr[]={1, 2, 3, 4}, k=2
Salida: Suma= 11
Suma = 1^2 + 2^3 + 3^4 = 3 + 1 + 7 =11
Entrada: arr[] ={1, 2, 3, 4}, k=3
Salida: Suma= 5
Suma = 1^2^3 + 2^3^4 = 0 + 5 =5
Solución ingenua: la idea es atravesar todos los subarreglos de longitud k y encontrar el xor de todos los elementos del subarreglo y sumarlos para encontrar la suma de XOR de todos los subarreglos de longitud K de un arreglo.
Complejidad de tiempo : O(N 2 )
Solución eficiente: La solución eficiente es recorrer el arreglo y encontrar todos los subarreglo de longitud k, es decir (0 a k-1), (1 a k), (2 a k+1) , …., (n-k+1 a n).
Encontraremos y almacenaremos el xor de los elementos de 0 a i (en una array x[]) formando una array pre-xor.
Ahora, xor del subarreglo de l a r es igual a x[l-1] ^ x[r] porque x[r] dará el xor de todos los elementos hasta r y x[l-1] dará el xor de todos los elementos hasta l-1. Cuando tomemos xor de estos dos valores se repetirán los elementos hasta 0 a l-1. Como a^a = 0, los valores repetidos contribuirían con cero al valor neto y obtenemos el valor de xor subarray de l a r.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach #include <iostream> using namespace std; // Sum of XOR of all K length // sub-array of an array int FindXorSum(int arr[], int k, int n) { // If the length of the array is less than k if (n < k) return 0; // Array that will store xor values of // subarray from 1 to i int x[n] = { 0 }; int result = 0; // Traverse through the array for (int i = 0; i < n; i++) { // If i is greater than zero, store // xor of all the elements from 0 to i if (i > 0) x[i] = x[i - 1] ^ arr[i]; // If it is the first element else x[i] = arr[i]; // If i is greater than k if (i >= k - 1) { int sum = 0; // Xor of values from 0 to i sum = x[i]; // Now to find subarray of length k // that ends at i, xor sum with x[i-k] if (i - k > -1) sum ^= x[i - k]; // Add the xor of elements from i-k+1 to i result += sum; } } // Return the resultant sum; return result; } // Driver code int main() { int arr[] = { 1, 2, 3, 4 }; int n = 4, k = 2; cout << FindXorSum(arr, k, n) << endl; return 0; }
Java
// Java implementation of the approach class GFG { // Sum of XOR of all K length // sub-array of an array static int FindXorSum(int arr[], int k, int n) { // If the length of the array is less than k if (n < k) return 0; // Array that will store xor values of // subarray from 1 to i int []x = new int[n]; int result = 0; // Traverse through the array for (int i = 0; i < n; i++) { // If i is greater than zero, store // xor of all the elements from 0 to i if (i > 0) x[i] = x[i - 1] ^ arr[i]; // If it is the first element else x[i] = arr[i]; // If i is greater than k if (i >= k - 1) { int sum = 0; // Xor of values from 0 to i sum = x[i]; // Now to find subarray of length k // that ends at i, xor sum with x[i-k] if (i - k > -1) sum ^= x[i - k]; // Add the xor of elements from i-k+1 to i result += sum; } } // Return the resultant sum; return result; } // Driver code public static void main(String[] args) { int arr[] = { 1, 2, 3, 4 }; int n = 4, k = 2; System.out.println(FindXorSum(arr, k, n)); } } // This code contributed by Rajput-Ji
Python3
# Python implementation of above approach # Sum of XOR of all K length # sub-array of an array def FindXorSum(arr, k, n): # If the length of the array is less than k if (n < k): return 0; # Array that will store xor values of # subarray from 1 to i x = [0]*n; result = 0; # Traverse through the array for i in range(n): # If i is greater than zero, store # xor of all the elements from 0 to i if (i > 0): x[i] = x[i - 1] ^ arr[i]; # If it is the first element else: x[i] = arr[i]; # If i is greater than k if (i >= k - 1): sum = 0; # Xor of values from 0 to i sum = x[i]; # Now to find subarray of length k # that ends at i, xor sum with x[i-k] if (i - k > -1): sum ^= x[i - k]; # Add the xor of elements from i-k+1 to i result += sum; # Return the resultant sum; return result; # Driver code arr = [ 1, 2, 3, 4 ]; n = 4; k = 2; print(FindXorSum(arr, k, n)); # This code has been contributed by 29AjayKumar
C#
// C# implementation of the above approach using System; class GFG { // Sum of XOR of all K length // sub-array of an array static int FindXorSum(int []arr, int k, int n) { // If the length of the array is less than k if (n < k) return 0; // Array that will store xor values of // subarray from 1 to i int []x = new int[n]; int result = 0; // Traverse through the array for (int i = 0; i < n; i++) { // If i is greater than zero, store // xor of all the elements from 0 to i if (i > 0) x[i] = x[i - 1] ^ arr[i]; // If it is the first element else x[i] = arr[i]; // If i is greater than k if (i >= k - 1) { int sum = 0; // Xor of values from 0 to i sum = x[i]; // Now to find subarray of length k // that ends at i, xor sum with x[i-k] if (i - k > -1) sum ^= x[i - k]; // Add the xor of elements from i-k+1 to i result += sum; } } // Return the resultant sum; return result; } // Driver code public static void Main() { int []arr = { 1, 2, 3, 4 }; int n = 4, k = 2; Console.WriteLine(FindXorSum(arr, k, n)); } } // This code is contributed by AnkitRai01
Javascript
<script> // Javascript implementation of above approach // Sum of XOR of all K length // sub-array of an array function FindXorSum(arr, k, n) { // If the length of the array is less than k if (n < k) return 0; // Array that will store xor values of // subarray from 1 to i let x = new Array(n).fill(0); let result = 0; // Traverse through the array for (let i = 0; i < n; i++) { // If i is greater than zero, store // xor of all the elements from 0 to i if (i > 0) x[i] = x[i - 1] ^ arr[i]; // If it is the first element else x[i] = arr[i]; // If i is greater than k if (i >= k - 1) { let sum = 0; // Xor of values from 0 to i sum = x[i]; // Now to find subarray of length k // that ends at i, xor sum with x[i-k] if (i - k > -1) sum ^= x[i - k]; // Add the xor of elements from i-k+1 to i result += sum; } } // Return the resultant sum; return result; } // Driver code let arr = [ 1, 2, 3, 4 ]; let n = 4, k = 2; document.write(FindXorSum(arr, k, n)); </script>
11
Complejidad de tiempo : O(N)
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA