Given an array of length n ( n > k), we have to find the sum of xor of all the elements of the sub-arrays which are of length k.
Examples:
Input : arr[]={1, 2, 3, 4}, k=2
Output :Sum= 11
Sum = 1^2 + 2^3 + 3^4 = 3 + 1 + 7 =11
Input :arr[]={1, 2, 3, 4}, k=3
Output :Sum= 5
Sum = 1^2^3 + 2^3^4 = 0 + 5 =5
Naive Solution: The idea is to traverse all the subarrays of length k and find the xor of all the elements of the subarray and sum them up to find the sum of XOR of all K length sub-array of an array.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Solution: The efficient solution is to traverse the array and find all the subarray of length k, i.e. ( 0 to k-1), (1 to k), (2 to k+1), …., (n-k+1 to n).
We will find and store the xor of elements from 0 to i (in an array x[]) by forming a pre-xor array.
Now, xor of sub array from l to r is equal to x[l-1] ^ x[r] because x[r] will give the xor of all elements till r and x[l-1] will give the xor of all elements till l-1. When we will take xor of these two values the elements till 0 to l-1 will be repeated. As a^a = 0, the repeated values would contribute zero to the net value and we get the value of xor sub array from l to r.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <iostream>using namespace std;// Sum of XOR of all K length// sub-array of an arrayint 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 codeint 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 approachclass GFG {// Sum of XOR of all K length// sub-array of an arraystatic 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 codepublic 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 codearr = [ 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 arrayfunction 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> |
Output:
11
Time Complexity: O(n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
