Posted on by Kalkicode
Code Mathematics

# 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)
{
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
--------------
*/
}
}``````

#### 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()
{
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
--------------
*/
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)
{
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
--------------

*/
}
}``````

#### 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()
{
\$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
--------------

*/
}
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 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
--------------

*/
}
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() :
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
#    --------------

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()
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
#    --------------
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
--------------

*/
}
}``````

#### 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 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
--------------

*/
}
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 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
--------------

*/
}``````

#### 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.

## 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.

Categories
Relative Post