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:
Initialize a variable
xor_sum
to 0, which will hold the XOR of all the elements in the array.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.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.
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
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