Skip to main content

Sum of XOR of all possible subsets

See an example.


Given set {1, 2, 3}

The subsets of the set are:
{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

The XOR of each subset can be calculated as follows:

XOR({1}) = 1
XOR({2}) = 2
XOR({3}) = 3
XOR({1,2}) = 1 XOR 2 = 3
XOR({1,3}) = 1 XOR 3 = 2
XOR({2,3}) = 2 XOR 3 = 1
XOR({1,2,3}) = 1 XOR 2 XOR 3 = 0
-----------------
1 + 2 + 3 + 3 + 2 + 1 = 12

The algorithm to calculate the sum of XOR of all possible subsets of a given array is as follows:

  1. Initialize a variable xor_sum to 0, which will hold the XOR of all the elements in the array.

  2. Loop through the array, and for each element, perform a bitwise OR operation with the current value of xor_sum. This will compute the XOR of all the elements in the array.

  3. Once the XOR of all the elements in the array has been computed, multiply it by 2^(n-1), where n is the length of the array. This will give us the sum of XOR of all possible subsets of the array.

  4. Print the result of the multiplication.

Code Solution

// C Program 
// Sum of XOR of all possible subsets
#include <stdio.h>

void sumSubsetsXor(int arr[], int n)
{
	if (n <= 0)
	{
		return;
	}
	int sum = 0;
	// Execute loop through byte array size
	for (int i = 0; i < n; i++)
	{
		// Sum of or element
		sum = sum | arr[i];
	}
	// Display calculated result
	printf("XOR Sum : %d", sum *(1 << n - 1));
}
int main()
{
	int arr[] = {
		6 , 2 , 5 , 3
	};
	// Get the size of arr
	int n = sizeof(arr) / sizeof(arr[0]);
	/*
	    (6) + (2) + (5) + (3) + 
	    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
	    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
	    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
	    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
	    --------------
	    56
	    --------------
	*/
	sumSubsetsXor(arr, n);
	return 0;
}

input

XOR Sum : 56
/*
   Java Program for
   Sum of XOR of all possible subsets
*/
public class Subarray
{
	public void sumSubsetsXor(int[] arr, int n)
	{
		if (n <= 0)
		{
			return;
		}
		int sum = 0;
		// Execute loop through byte array size
		for (int i = 0; i < n; i++)
		{
			// Sum of or element
			sum = sum | arr[i];
		}
		// Display calculated result
		System.out.print("XOR Sum : " + (sum * (1 << n - 1)));
	}
	public static void main(String[] args)
	{
		Subarray task = new Subarray();
		int[] arr = {
			6 , 2 , 5 , 3
		};
		// Get the size of arr
		int n = arr.length;
		/*
		    (6) + (2) + (5) + (3) + 
		    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
		    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
		    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
		    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
		    --------------
		    56
		    --------------
		*/
		task.sumSubsetsXor(arr, n);
	}
}

input

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

using namespace std;
/*
   C++ Program for
   Sum of XOR of all possible subsets
*/
class Subarray
{
	public: void sumSubsetsXor(int arr[], int n)
	{
		if (n <= 0)
		{
			return;
		}
		int sum = 0;
		// Execute loop through byte array size
		for (int i = 0; i < n; i++)
		{
			// Sum of or element
			sum = sum | arr[i];
		}
		// Display calculated result
		cout << "XOR Sum : " << (sum *(1 << n - 1));
	}
};
int main()
{
	Subarray *task = new Subarray();
	int arr[] = {
		6 , 2 , 5 , 3
	};
	// Get the size of arr
	int n = sizeof(arr) / sizeof(arr[0]);
	/*
	    (6) + (2) + (5) + (3) + 
	    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
	    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
	    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
	    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
	    --------------
	    56
	    --------------
	*/
	task->sumSubsetsXor(arr, n);
	return 0;
}

input

XOR Sum : 56
// Include namespace system
using System;
/*
   Csharp Program for
   Sum of XOR of all possible subsets
*/
public class Subarray
{
	public void sumSubsetsXor(int[] arr, int n)
	{
		if (n <= 0)
		{
			return;
		}
		int sum = 0;
		// Execute loop through byte array size
		for (int i = 0; i < n; i++)
		{
			// Sum of or element
			sum = sum | arr[i];
		}
		// Display calculated result
		Console.Write("XOR Sum : " + (sum * (1 << n - 1)));
	}
	public static void Main(String[] args)
	{
		Subarray task = new Subarray();
		int[] arr = {
			6 , 2 , 5 , 3
		};
		// Get the size of arr
		int n = arr.Length;
		/*
		    (6) + (2) + (5) + (3) + 
		    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
		    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
		    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
		    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
		    --------------
		    56
		    --------------
		*/
		task.sumSubsetsXor(arr, n);
	}
}

input

XOR Sum : 56
<?php
/*
   Php Program for
   Sum of XOR of all possible subsets
*/
class Subarray
{
	public	function sumSubsetsXor($arr, $n)
	{
		if ($n <= 0)
		{
			return;
		}
		$sum = 0;
		// Execute loop through byte array size
		for ($i = 0; $i < $n; $i++)
		{
			// Sum of or element
			$sum = $sum | $arr[$i];
		}
		// Display calculated result
		echo("XOR Sum : ".($sum * (1 << $n - 1)));
	}
}

function main()
{
	$task = new Subarray();
	$arr = array(6, 2, 5, 3);
	// Get the size of arr
	$n = count($arr);
	/*
	    (6) + (2) + (5) + (3) + 
	    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
	    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
	    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
	    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
	    --------------
	    56
	    --------------
	*/
	$task->sumSubsetsXor($arr, $n);
}
main();

input

XOR Sum : 56
/*
   Node JS Program for
   Sum of XOR of all possible subsets
*/
class Subarray
{
	sumSubsetsXor(arr, n)
	{
		if (n <= 0)
		{
			return;
		}
		var sum = 0;
		// Execute loop through byte array size
		for (var i = 0; i < n; i++)
		{
			// Sum of or element
			sum = sum | arr[i];
		}
		// Display calculated result
		process.stdout.write("XOR Sum : " + (sum * (1 << n - 1)));
	}
}

function main()
{
	var task = new Subarray();
	var arr = [6, 2, 5, 3];
	// Get the size of arr
	var n = arr.length;
	/*
	    (6) + (2) + (5) + (3) + 
	    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
	    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
	    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
	    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
	    --------------
	    56
	    --------------
	*/
	task.sumSubsetsXor(arr, n);
}
main();

input

XOR Sum : 56
#   Python 3 Program for
#   Sum of XOR of all possible subsets
class Subarray :
	def sumSubsetsXor(self, arr, n) :
		if (n <= 0) :
			return
		
		sum = 0
		i = 0
		#  Execute loop through byte list size
		while (i < n) :
			#  Sum of or element
			sum = sum | arr[i]
			i += 1
		
		#  Display calculated result
		print("XOR Sum : ", (sum * (1 << n - 1)), end = "")
	

def main() :
	task = Subarray()
	arr = [6, 2, 5, 3]
	#  Get the size of arr
	n = len(arr)
	#    (6) + (2) + (5) + (3) + 
	#    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
	#    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
	#    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
	#    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
	#    --------------
	#    56
	#    --------------
	task.sumSubsetsXor(arr, n)

if __name__ == "__main__": main()

input

XOR Sum :  56
#   Ruby Program for
#   Sum of XOR of all possible subsets
class Subarray 
	def sumSubsetsXor(arr, n) 
		if (n <= 0) 
			return
		end

		sum = 0
		i = 0
		#  Execute loop through byte array size
		while (i < n) 
			#  Sum of or element
			sum = sum | arr[i]
			i += 1
		end

		#  Display calculated result
		print("XOR Sum : ", (sum * (1 << n - 1)))
	end

end

def main() 
	task = Subarray.new()
	arr = [6, 2, 5, 3]
	#  Get the size of arr
	n = arr.length
	#    (6) + (2) + (5) + (3) + 
	#    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
	#    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
	#    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
	#    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
	#    --------------
	#    56
	#    --------------
	task.sumSubsetsXor(arr, n)
end

main()

input

XOR Sum : 56
/*
   Scala Program for
   Sum of XOR of all possible subsets
*/
class Subarray()
{
	def sumSubsetsXor(arr: Array[Int], n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		var sum: Int = 0;
		var i: Int = 0;
		// Execute loop through byte array size
		while (i < n)
		{
			// Sum of or element
			sum = sum | arr(i);
			i += 1;
		}
		// Display calculated result
		print("XOR Sum : " + (sum * (1 << n - 1)));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subarray = new Subarray();
		var arr: Array[Int] = Array(6, 2, 5, 3);
		// Get the size of arr
		var n: Int = arr.length;
		/*
		    (6) + (2) + (5) + (3) + 
		    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
		    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
		    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
		    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
		    --------------
		    56
		    --------------
		*/
		task.sumSubsetsXor(arr, n);
	}
}

input

XOR Sum : 56
import Foundation;
/*
   Swift 4 Program for
   Sum of XOR of all possible subsets
*/
class Subarray
{
	func sumSubsetsXor(_ arr: [Int], _ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		var sum = 0;
		var i = 0;
		// Execute loop through byte array size
		while (i < n)
		{
			// Sum of or element
			sum = sum | arr[i];
			i += 1;
		}
		// Display calculated result
		print("XOR Sum : ", (sum * (1 << (n - 1))), terminator: "");
	}
}
func main()
{
	let task = Subarray();
	let arr = [6, 2, 5, 3];
	// Get the size of arr
	let n = arr.count;
	/*
	    (6) + (2) + (5) + (3) + 
	    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
	    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
	    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
	    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
	    --------------
	    56
	    --------------
	*/
	task.sumSubsetsXor(arr, n);
}
main();

input

XOR Sum :  56
/*
   Kotlin Program for
   Sum of XOR of all possible subsets
*/
class Subarray
{
	fun sumSubsetsXor(arr: Array < Int > , n: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		var sum: Int = 0;
		var i: Int = 0;
		// Execute loop through byte array size
		while (i < n)
		{
			// Sum of or element
			sum = sum or arr[i];
			i += 1;
		}
		// Display calculated result
		print("XOR Sum : " + (sum * (1 shl (n - 1))));
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subarray = Subarray();
	val arr: Array < Int > = arrayOf(6, 2, 5, 3);
	// Get the size of arr
	val n: Int = arr.count();
	/*
	    (6) + (2) + (5) + (3) + 
	    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
	    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
	    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
	    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
	    --------------
	    56
	    --------------
	*/
	task.sumSubsetsXor(arr, n);
}

input

XOR Sum : 56
package main
import "fmt"
/*
   Go Program for
   Sum of XOR of all possible subsets
*/

func sumSubsetsXor(arr[] int, n int) {
	if n <= 0 {
		return
	}
	var sum int = 0
	// Execute loop through byte array size
	for i := 0 ; i < n ; i++ {
		// Sum of or element
		sum = sum | arr[i]
	}
	// Display calculated result
	fmt.Print("XOR Sum : ", (sum * (1 << (n - 1))))
}
func main() {
	
	var arr = [] int {
		6,
		2,
		5,
		3,
	}
	// Get the size of arr
	var n int = len(arr)
	/*
	    (6) + (2) + (5) + (3) + 
	    (6 ^ 2) + (6 ^ 5) + (6 ^ 3) + 
	    (2 ^ 5) + (2 ^ 3) + (5 ^ 3) + 
	    (6 ^ 2 ^ 5) + (6 ^ 2 ^ 3) + 
	    (6 ^ 5 ^ 3) + (2 ^ 5 ^ 3) + (6 ^ 2 ^ 5 ^ 3)
	    --------------
	    56
	    --------------
	*/
	sumSubsetsXor(arr, n)
}

input

XOR Sum : 56
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