Skip to main content

Sum of XOR of all subarrays

The problem at hand is to calculate the sum of XOR of all subarrays of a given array. In simpler terms, given an array of integers, we want to find the XOR of all possible subarrays and then sum up those XOR values.

Problem Statement

Given an array of integers, the task is to find the sum of the XOR values of all subarrays that can be formed from the given array.

Description

To better understand the problem, let's take an example. Consider the array: [7, 2, 5, 1].

  1. Subarrays of length 1: [7], [2], [5], [1]. XOR of each subarray is [7], [2], [5], [1] respectively.
  2. Subarrays of length 2: [7, 2], [2, 5], [5, 1]. XOR of each subarray is [5], [7], [4] respectively.
  3. Subarrays of length 3: [7, 2, 5], [2, 5, 1]. XOR of each subarray is [0], [6] respectively.
  4. Subarray of length 4: [7, 2, 5, 1]. XOR of the subarray is [5].

Now, if we sum up all these XOR values: 7 + 2 + 5 + 1 + 5 + 7 + 4 + 0 + 6 + 5 = 38. This is the desired result.

Idea to Solve

To efficiently solve this problem, we can observe that the XOR operation is bitwise in nature. We can focus on the individual bits of the array elements and count the occurrences of 1s in those bits. Based on this observation, we can formulate an algorithm to calculate the sum of XOR values for all subarrays.

Algorithm

  1. Initialize variables sum to store the final result, multiplier to keep track of the power of 2, oddBits to count the odd occurrences of 1s, and isOdd to indicate whether the oddBits count is currently odd or even.

  2. Loop through each bit position from 0 to 29 (assuming the array elements are 32-bit integers): a. Initialize oddBits to 0 and isOdd to false. b. Loop through each element in the array: i. If the current bit at the bit position is 1, toggle the isOdd flag. ii. If isOdd is true, increment oddBits. c. Loop through each element in the array: i. Update the sum by adding multiplier * oddBits. ii. If the current bit at the bit position is 1, update oddBits to (n - j - oddBits).

  3. After both inner loops finish, reset isOdd to false and oddBits to 0.

  4. Multiply multiplier by 2.

  5. Repeat steps 2-4 for all bit positions.

  6. Print the final value of sum.

Pseudocode

sumSubarrayXor(arr[], n):
    sum = 0
    multiplier = 1
    oddBits = 0
    isOdd = false
    
    for i = 0 to 29:
        oddBits = 0
        isOdd = false
        
        for j = 0 to n - 1:
            if (arr[j] & (1 << i)) != 0:
                isOdd = !isOdd
            if isOdd:
                oddBits++
        
        for j = 0 to n - 1:
            sum = sum + (multiplier * oddBits)
            if (arr[j] & (1 << i)) != 0:
                oddBits = n - j - oddBits
        
        isOdd = false
        oddBits = 0
        multiplier = multiplier * 2
    
    print("XOR Sum:", sum)

Code Solution

// C Program 
// Sum of XOR of all subarrays
#include <stdio.h>
#include <stdbool.h>

void sumSubarrayXor(int arr[], int n)
{
	// Define some auxiliary variables
	int sum = 0;
	int multiplier = 1;
	int oddBits = 0;
	bool isOdd = false;
	// Working on initial 30 bits
	for (int i = 0; i < 30; i++)
	{
		// Count active bits in alternate elements 
		for (int j = 0; j < n; j++)
		{
			// Check (1 << i) bit is active or not
			if ((arr[j] & (1 << i)) != 0)
			{
				// Change the status
				isOdd = !isOdd;
			}
			if (isOdd == true)
			{
				// Increase counter position
				oddBits++;
			}
		}
		for (int j = 0; j < n; j++)
		{
			// Change resultant sum
			sum = sum + (multiplier * oddBits);
			if ((arr[j] & (1 << i)) != 0)
			{
				oddBits = (n - j - oddBits);
			}
		}
		// Reset odd counter indicator
		isOdd = false;
		oddBits = 0;
		// Increase the multiplier by twice
		multiplier = multiplier * 2;
	}
	// Display calculated result
	printf("XOR Sum : %d", sum);
}
int main()
{
	int arr[] = {
		7 , 2 , 5 , 1
	};
	// Get the size of arr
	int n = sizeof(arr) / sizeof(arr[0]);
	/*
	    (7) + (2) + (5) + (1) + 
	    (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
	    (7^ 2^ 5) + (2^ 5 ^ 1) +
	    (7^ 2^ 5^ 1)
	    --------------
	    38
	    --------------
	*/
	sumSubarrayXor(arr, n);
	return 0;
}

input

XOR Sum : 38
/*
    Java Program for
    Sum of XOR of all subarrays
*/
public class Subarray
{
    public void sumSubarrayXor(int[] arr, int n)
    {
        // Define some auxiliary variables
        int sum = 0;
        int multiplier = 1;
        int oddBits = 0;
        boolean isOdd = false;
        // Working on initial 30 bits
        for (int i = 0; i < 30; i++)
        {
            // Count active bits in alternate elements
            for (int j = 0; j < n; j++)
            {
                // Check (1 << i) bit is active or not
                if ((arr[j] & (1 << i)) != 0)
                {
                    // Change the status
                    isOdd = !isOdd;
                }
                if (isOdd == true)
                {
                    // Increase counter position
                    oddBits++;
                }
            }
            for (int j = 0; j < n; j++)
            {
                // Change resultant sum
                sum = sum + (multiplier * oddBits);
                if ((arr[j] & (1 << i)) != 0)
                {
                    oddBits = (n - j - oddBits);
                }
            }
            // Reset odd counter indicator
            isOdd = false;
            oddBits = 0;
            // Increase the multiplier by twice
            multiplier = multiplier * 2;
        }
        // Display calculated result
        System.out.print("XOR Sum : " + sum);
    }
    public static void main(String[] args)
    {
        Subarray task = new Subarray();
        int[] arr = {
            7 , 2 , 5 , 1
        };
        // Get the size of arr
        int n = arr.length;
        /*
            (7) + (2) + (5) + (1) + 
            (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
            (7^ 2^ 5) + (2^ 5 ^ 1) +
            (7^ 2^ 5^ 1)
            --------------
            38
            --------------         
        */
        task.sumSubarrayXor(arr, n);
    }
}

input

XOR Sum : 38
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program for
    Sum of XOR of all subarrays
*/
class Subarray
{
	public: void sumSubarrayXor(int arr[], int n)
	{
		// Define some auxiliary variables
		int sum = 0;
		int multiplier = 1;
		int oddBits = 0;
		bool isOdd = false;
		// Working on initial 30 bits
		for (int i = 0; i < 30; i++)
		{
			// Count active bits in alternate elements
			for (int j = 0; j < n; j++)
			{
				// Check (1 << i) bit is active or not
				if ((arr[j] &(1 << i)) != 0)
				{
					// Change the status
					isOdd = !isOdd;
				}
				if (isOdd == true)
				{
					// Increase counter position
					oddBits++;
				}
			}
			for (int j = 0; j < n; j++)
			{
				// Change resultant sum
				sum = sum + (multiplier *oddBits);
				if ((arr[j] &(1 << i)) != 0)
				{
					oddBits = (n - j - oddBits);
				}
			}
			// Reset odd counter indicator
			isOdd = false;
			oddBits = 0;
			// Increase the multiplier by twice
			multiplier = multiplier *2;
		}
		// Display calculated result
		cout << "XOR Sum : " << sum;
	}
};
int main()
{
	Subarray *task = new Subarray();
	int arr[] = {7 , 2 , 5 , 1};
	// Get the size of arr
	int n = sizeof(arr) / sizeof(arr[0]);
	/*
	    (7) + (2) + (5) + (1) + 
	    (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
	    (7^ 2^ 5) + (2^ 5 ^ 1) +
	    (7^ 2^ 5^ 1)
	    --------------
	    38
	    --------------         
	*/
	task->sumSubarrayXor(arr, n);
	return 0;
}

input

XOR Sum : 38
// Include namespace system
using System;
/*
    Csharp Program for
    Sum of XOR of all subarrays
*/
public class Subarray
{
	public void sumSubarrayXor(int[] arr, int n)
	{
		// Define some auxiliary variables
		int sum = 0;
		int multiplier = 1;
		int oddBits = 0;
		Boolean isOdd = false;
		// Working on initial 30 bits
		for (int i = 0; i < 30; i++)
		{
			// Count active bits in alternate elements
			for (int j = 0; j < n; j++)
			{
				// Check (1 << i) bit is active or not
				if ((arr[j] & (1 << i)) != 0)
				{
					// Change the status
					isOdd = !isOdd;
				}
				if (isOdd == true)
				{
					// Increase counter position
					oddBits++;
				}
			}
			for (int j = 0; j < n; j++)
			{
				// Change resultant sum
				sum = sum + (multiplier * oddBits);
				if ((arr[j] & (1 << i)) != 0)
				{
					oddBits = (n - j - oddBits);
				}
			}
			// Reset odd counter indicator
			isOdd = false;
			oddBits = 0;
			// Increase the multiplier by twice
			multiplier = multiplier * 2;
		}
		// Display calculated result
		Console.Write("XOR Sum : " + sum);
	}
	public static void Main(String[] args)
	{
		Subarray task = new Subarray();
		int[] arr = {
			7 , 2 , 5 , 1
		};
		// Get the size of arr
		int n = arr.Length;
		/*
		    (7) + (2) + (5) + (1) + 
		    (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
		    (7^ 2^ 5) + (2^ 5 ^ 1) +
		    (7^ 2^ 5^ 1)
		    --------------
		    38
		    --------------         
		        
		*/
		task.sumSubarrayXor(arr, n);
	}
}

input

XOR Sum : 38
<?php
/*
    Php Program for
    Sum of XOR of all subarrays
*/
class Subarray
{
	public	function sumSubarrayXor($arr, $n)
	{
		// Define some auxiliary variables
		$sum = 0;
		$multiplier = 1;
		$oddBits = 0;
		$isOdd = false;
		// Working on initial 30 bits
		for ($i = 0; $i < 30; $i++)
		{
			// Count active bits in alternate elements
			for ($j = 0; $j < $n; $j++)
			{
				// Check (1 << i) bit is active or not
				if (($arr[$j] & (1 << $i)) != 0)
				{
					// Change the status
					$isOdd = !$isOdd;
				}
				if ($isOdd == true)
				{
					// Increase counter position
					$oddBits++;
				}
			}
			for ($j = 0; $j < $n; $j++)
			{
				// Change resultant sum
				$sum = $sum + ($multiplier * $oddBits);
				if (($arr[$j] & (1 << $i)) != 0)
				{
					$oddBits = ($n - $j - $oddBits);
				}
			}
			// Reset odd counter indicator
			$isOdd = false;
			$oddBits = 0;
			// Increase the multiplier by twice
			$multiplier = $multiplier * 2;
		}
		// Display calculated result
		echo("XOR Sum : ".$sum);
	}
}

function main()
{
	$task = new Subarray();
	$arr = array(7, 2, 5, 1);
	// Get the size of arr
	$n = count($arr);
	/*
	    (7) + (2) + (5) + (1) + 
	    (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
	    (7^ 2^ 5) + (2^ 5 ^ 1) +
	    (7^ 2^ 5^ 1)
	    --------------
	    38
	    --------------         
	        
	*/
	$task->sumSubarrayXor($arr, $n);
}
main();

input

XOR Sum : 38
/*
    Node JS Program for
    Sum of XOR of all subarrays
*/
class Subarray
{
	sumSubarrayXor(arr, n)
	{
		// Define some auxiliary variables
		var sum = 0;
		var multiplier = 1;
		var oddBits = 0;
		var isOdd = false;
		// Working on initial 30 bits
		for (var i = 0; i < 30; i++)
		{
			// Count active bits in alternate elements
			for (var j = 0; j < n; j++)
			{
				// Check (1 << i) bit is active or not
				if ((arr[j] & (1 << i)) != 0)
				{
					// Change the status
					isOdd = !isOdd;
				}
				if (isOdd == true)
				{
					// Increase counter position
					oddBits++;
				}
			}
			for (var j = 0; j < n; j++)
			{
				// Change resultant sum
				sum = sum + (multiplier * oddBits);
				if ((arr[j] & (1 << i)) != 0)
				{
					oddBits = (n - j - oddBits);
				}
			}
			// Reset odd counter indicator
			isOdd = false;
			oddBits = 0;
			// Increase the multiplier by twice
			multiplier = multiplier * 2;
		}
		// Display calculated result
		process.stdout.write("XOR Sum : " + sum);
	}
}

function main()
{
	var task = new Subarray();
	var arr = [7, 2, 5, 1];
	// Get the size of arr
	var n = arr.length;
	/*
	    (7) + (2) + (5) + (1) + 
	    (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
	    (7^ 2^ 5) + (2^ 5 ^ 1) +
	    (7^ 2^ 5^ 1)
	    --------------
	    38
	    --------------         
	        
	*/
	task.sumSubarrayXor(arr, n);
}
main();

input

XOR Sum : 38
#    Python 3 Program for
#    Sum of XOR of all subarrays
class Subarray :
	def sumSubarrayXor(self, arr, n) :
		#  Define some auxiliary variables
		sum = 0
		multiplier = 1
		oddBits = 0
		isOdd = False
		i = 0
		#  Working on initial 30 bits
		while (i < 30) :
			j = 0
			#  Count active bits in alternate elements
			while (j < n) :
				#  Check (1 << i) bit is active or not
				if ((arr[j] & (1 << i)) != 0) :
					#  Change the status
					isOdd = not isOdd
				
				if (isOdd == True) :
					#  Increase counter position
					oddBits += 1
				
				j += 1
			
			j = 0
			while (j < n) :
				#  Change resultant sum
				sum = sum + (multiplier * oddBits)
				if ((arr[j] & (1 << i)) != 0) :
					oddBits = (n - j - oddBits)
				
				j += 1
			
			#  Reset odd counter indicator
			isOdd = False
			oddBits = 0
			#  Increase the multiplier by twice
			multiplier = multiplier * 2
			i += 1
		
		#  Display calculated result
		print("XOR Sum : ", sum, end = "")
	

def main() :
	task = Subarray()
	arr = [7, 2, 5, 1]
	#  Get the size of arr
	n = len(arr)
	#    (7) + (2) + (5) + (1) + 
	#    (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
	#    (7^ 2^ 5) + (2^ 5 ^ 1) +
	#    (7^ 2^ 5^ 1)
	#    --------------
	#    38
	#    --------------         
	task.sumSubarrayXor(arr, n)

if __name__ == "__main__": main()

input

XOR Sum :  38
#    Ruby Program for
#    Sum of XOR of all subarrays
class Subarray 
	def sumSubarrayXor(arr, n) 
		#  Define some auxiliary variables
		sum = 0
		multiplier = 1
		oddBits = 0
		isOdd = false
		i = 0
		#  Working on initial 30 bits
		while (i < 30) 
			j = 0
			#  Count active bits in alternate elements
			while (j < n) 
				#  Check (1 << i) bit is active or not
				if ((arr[j] & (1 << i)) != 0) 
					#  Change the status
					isOdd = !isOdd
				end

				if (isOdd == true) 
					#  Increase counter position
					oddBits += 1
				end

				j += 1
			end

			j = 0
			while (j < n) 
				#  Change resultant sum
				sum = sum + (multiplier * oddBits)
				if ((arr[j] & (1 << i)) != 0) 
					oddBits = (n - j - oddBits)
				end

				j += 1
			end

			#  Reset odd counter indicator
			isOdd = false
			oddBits = 0
			#  Increase the multiplier by twice
			multiplier = multiplier * 2
			i += 1
		end

		#  Display calculated result
		print("XOR Sum : ", sum)
	end

end

def main() 
	task = Subarray.new()
	arr = [7, 2, 5, 1]
	#  Get the size of arr
	n = arr.length
	#    (7) + (2) + (5) + (1) + 
	#    (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
	#    (7^ 2^ 5) + (2^ 5 ^ 1) +
	#    (7^ 2^ 5^ 1)
	#    --------------
	#    38
	#    --------------         
	task.sumSubarrayXor(arr, n)
end

main()

input

XOR Sum : 38
/*
    Scala Program for
    Sum of XOR of all subarrays
*/
class Subarray()
{
	def sumSubarrayXor(arr: Array[Int], n: Int): Unit = {
		// Define some auxiliary variables
		var sum: Int = 0;
		var multiplier: Int = 1;
		var oddBits: Int = 0;
		var isOdd: Boolean = false;
		var i: Int = 0;
		// Working on initial 30 bits
		while (i < 30)
		{
			var j: Int = 0;
			// Count active bits in alternate elements
			while (j < n)
			{
				// Check (1 << i) bit is active or not
				if ((arr(j) & (1 << i)) != 0)
				{
					// Change the status
					isOdd = !isOdd;
				}
				if (isOdd == true)
				{
					// Increase counter position
					oddBits += 1;
				}
				j += 1;
			}
			j  = 0;
			while (j < n)
			{
				// Change resultant sum
				sum = sum + (multiplier * oddBits);
				if ((arr(j) & (1 << i)) != 0)
				{
					oddBits = (n - j - oddBits);
				}
				j += 1;
			}
			// Reset odd counter indicator
			isOdd = false;
			oddBits = 0;
			// Increase the multiplier by twice
			multiplier = multiplier * 2;
			i += 1;
		}
		// Display calculated result
		print("XOR Sum : " + sum);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subarray = new Subarray();
		var arr: Array[Int] = Array(7, 2, 5, 1);
		// Get the size of arr
		var n: Int = arr.length;
		/*
		    (7) + (2) + (5) + (1) + 
		    (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
		    (7^ 2^ 5) + (2^ 5 ^ 1) +
		    (7^ 2^ 5^ 1)
		    --------------
		    38
		    --------------         
		        
		*/
		task.sumSubarrayXor(arr, n);
	}
}

input

XOR Sum : 38
import Foundation;
/*
    Swift 4 Program for
    Sum of XOR of all subarrays
*/
class Subarray
{
	func sumSubarrayXor(_ arr: [Int], _ n: Int)
	{
		// Define some auxiliary variables
		var sum = 0;
		var multiplier = 1;
		var oddBits = 0;
		var isOdd = false;
		var i = 0;
		// Working on initial 30 bits
		while (i < 30)
		{
			var j = 0;
			// Count active bits in alternate elements
			while (j < n)
			{
				// Check (1 << i) bit is active or not
				if ((arr[j] & (1 << i))  != 0)
				{
					// Change the status
					isOdd = !isOdd;
				}
				if (isOdd == true)
				{
					// Increase counter position
					oddBits += 1;
				}
				j += 1;
			}
			j = 0;
			while (j < n)
			{
				// Change resultant sum
				sum = sum + (multiplier * oddBits);
				if ((arr[j] & (1 << i))  != 0)
				{
					oddBits = (n - j - oddBits);
				}
				j += 1;
			}
			// Reset odd counter indicator
			isOdd = false;
			oddBits = 0;
			// Increase the multiplier by twice
			multiplier = multiplier * 2;
			i += 1;
		}
		// Display calculated result
		print("XOR Sum : ", sum, terminator: "");
	}
}
func main()
{
	let task = Subarray();
	let arr = [7, 2, 5, 1];
	// Get the size of arr
	let n = arr.count;
	/*
	    (7) + (2) + (5) + (1) + 
	    (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
	    (7^ 2^ 5) + (2^ 5 ^ 1) +
	    (7^ 2^ 5^ 1)
	    --------------
	    38
	    --------------         
	        
	*/
	task.sumSubarrayXor(arr, n);
}
main();

input

XOR Sum :  38
/*
    Kotlin Program for
    Sum of XOR of all subarrays
*/
class Subarray
{
	fun sumSubarrayXor(arr: Array < Int > , n: Int): Unit
	{
		// Define some auxiliary variables
		var sum: Int = 0;
		var multiplier: Int = 1;
		var oddBits: Int = 0;
		var isOdd: Boolean = false;
		var i: Int = 0;
		// Working on initial 30 bits
		while (i < 30)
		{
			var j: Int = 0;
			// Count active bits in alternate elements
			while (j < n)
			{
				// Check (1 << i) bit is active or not
				if ((arr[j] and(1 shl i)) != 0)
				{
					// Change the status
					isOdd = !isOdd;
				}
				if (isOdd == true)
				{
					// Increase counter position
					oddBits += 1;
				}
				j += 1;
			}
			j = 0;
			while (j < n)
			{
				// Change resultant sum
				sum = sum + (multiplier * oddBits);
				if ((arr[j] and(1 shl i)) != 0)
				{
					oddBits = (n - j - oddBits);
				}
				j += 1;
			}
			// Reset odd counter indicator
			isOdd = false;
			oddBits = 0;
			// Increase the multiplier by twice
			multiplier = multiplier * 2;
			i += 1;
		}
		// Display calculated result
		print("XOR Sum : " + sum);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subarray = Subarray();
	val arr: Array < Int > = arrayOf(7, 2, 5, 1);
	// Get the size of arr
	val n: Int = arr.count();
	/*
	    (7) + (2) + (5) + (1) + 
	    (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
	    (7^ 2^ 5) + (2^ 5 ^ 1) +
	    (7^ 2^ 5^ 1)
	    --------------
	    38
	    --------------         
	        
	*/
	task.sumSubarrayXor(arr, n);
}

input

XOR Sum : 38
package main
import "fmt"
/*
    Go Program for
    Sum of XOR of all subarrays
*/

func sumSubarrayXor(arr[] int, n int) {
	// Define some auxiliary variables
	var sum int = 0
	var multiplier int = 1
	var oddBits int = 0
	var isOdd bool = false
	// Working on initial 30 bits
	for i := 0 ; i < 30 ; i++ {
		// Count active bits in alternate elements
		for j := 0 ; j < n ; j++ {
			// Check (1 << i) bit is active or not
			if (arr[j] & (1 << i)) != 0 {
				// Change the status
				isOdd = !isOdd
			}
			if isOdd == true {
				// Increase counter position
				oddBits++
			}
		}
		for j := 0 ; j < n ; j++ {
			// Change resultant sum
			sum = sum + (multiplier * oddBits)
			if (arr[j] & (1 << i)) != 0 {
				oddBits = (n - j - oddBits)
			}
		}
		// Reset odd counter indicator
		isOdd = false
		oddBits = 0
		// Increase the multiplier by twice
		multiplier = multiplier * 2
	}
	// Display calculated result
	fmt.Print("XOR Sum : ", sum)
}
func main() {

	var arr = [] int {
		7,
		2,
		5,
		1,
	}
	// Get the size of arr
	var n int = len(arr)
	/*
	    (7) + (2) + (5) + (1) + 
	    (7 ^ 2) + (2 ^ 5) + (5 ^ 1) + 
	    (7^ 2^ 5) + (2^ 5 ^ 1) +
	    (7^ 2^ 5^ 1)
	    --------------
	    38
	    --------------         
	        
	*/
	sumSubarrayXor(arr, n)
}

input

XOR Sum : 38

Time Complexity

The time complexity of this algorithm is O(N * 30), which simplifies to O(N) since the inner loops run a constant number of times (30 times) regardless of the input size N.

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment