Sum of XOR of all sub-arrays of length K

0 0 6 minutes read

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(N²)
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 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>

Output:

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 zambiatek!