Suma de XOR de la suma de todos los pares en una array

Dada una array, encuentre el XOR de la suma de todos los pares en una array.
Ejemplos: 
 

Input  : arr[] = {1, 2, 3}
Output : 0
(1 + 1) ^ (1 + 2) ^ (1 + 3) ^ (2 + 1) ^ (2 + 2) ^ 
(2 + 3) ^ (3 + 1) ^ (3 + 2) ^ (3 + 3) = 0

Input  : arr[] = {1, 2, 3, 4}
Output : 8

Un enfoque ingenuo es considerar todos los pares uno por uno, calcular su XOR uno tras otro. 
 

// CPP program to find XOR of pair
// sums.
#include <bits/stdc++.h>
 
using namespace std;
 
int xorPairSum(int ar[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sum = sum ^ (ar[i] + ar[j]);
    return sum;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << xorPairSum(arr, n);
    return 0;
}

// Java program to find XOR of pair sums.
import java.io.*;
  
class GFG {
 
// method to find XOR of pair sums
static int xorPairSum(int ar[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sum = sum ^ (ar[i] + ar[j]);
    return sum;
}
  
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = {1, 2, 3};
        int n = arr.length;
        System.out.print( xorPairSum(arr, n));
    }
}
 
// This code is contributed by chandan_jnu.

# Python program to find
# XOR of pair sums.
 
def xor_pair_sum(ar, n):
    total = 0
    for i in range(n):
        for j in range(n):
            total = total ^ (ar[i] + ar[j])
 
    return total
 
 
# Driver program to test the above function
if __name__ == "__main__":
    data = [1, 2, 3]
    print(xor_pair_sum(data, len(data)))
 
# This code is contributed
# by Kanav Malhotra

// C# program to find
// XOR of pair sums.
using System;
 
class GFG
{
static int xorPairSum(int []ar,
                    int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sum = sum ^ (ar[i] + ar[j]);
    return sum;
}
 
// Driver code
static public void Main(String []args)
{
    int []arr = { 1, 2, 3 };
    int n = arr.Length;
    Console.WriteLine(xorPairSum(arr, n));
}
}
 
// This code is contributed
// by Arnab Kundu

<?php
// PHP program to find
// XOR of pair sums.
 
function xorPairSum($ar, $n)
{
    $sum = 0;
    for ($i = 0; $i < $n; $i++)
        $sum = $sum ^ ($ar[$i] +
                       $ar[$j]);
    return $sum;
}
 
// Driver code
$arr = array( 1, 2, 3 );
$n = count($arr);
echo xorPairSum($arr, $n);
 
// This code is contributed
// by Subhadeep
?>

<script>
 
// JavaScript program to find XOR of pair
// sums.
 
function xorPairSum(ar, n)
{
    let sum = 0;
    for (let i = 0; i < n; i++)
        for (let j = 0; j < n; j++)
            sum = sum ^ (ar[i] + ar[j]);
    return sum;
}
 
// Driver code
 
    let arr = [ 1, 2, 3 ];
    let n = arr.length;
    document.write(xorPairSum(arr, n));
 
// This code is contributed by Surbhi Tyagi
 
</script>

0

Complejidad temporal: O(N ² )
Una solución eficiente se basa en las propiedades XOR. Simplemente calculamos el XOR de cada elemento y luego lo multiplicamos por dos. 
 

// CPP program to find XOR of pair
// sums.
#include <bits/stdc++.h>
 
using namespace std;
 
int xorPairSum(int ar[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
       sum = sum ^ ar[i];
    return 2*sum;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 3 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << xorPairSum(arr, n);
    return 0;
}

// Java program to find
// XOR of pair sums.
class GFG
{
     
static int xorPairSum(int ar[],
                      int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    sum = sum ^ ar[i];
    return 2 * sum;
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 1, 2, 3 };
    int n = arr.length;
    System.out.println( xorPairSum(arr, n));
}
}
 
// This code is contributed
// by Arnab Kundu

# Python3 program to find
# XOR of pair sums.
 
def xor_pair_sum(ar, n):
    total = 0
    for i in range(n):
        total = total ^ ar[i]
 
    return 2 * total
 
 
# Driver program to test the above function
if __name__ == "__main__":
    data = [1, 2, 3]
    print(xor_pair_sum(data, len(data)))
 
# This code is contributed
# by Kanav Malhotra

// C# program to find
// XOR of pair sums.
using System;
 
class GFG
{
     
static int xorPairSum(int []ar,
                    int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    sum = sum ^ ar[i];
    return 2 * sum;
}
 
// Driver code
static public void Main(String []args)
{
    int []arr = { 1, 2, 3 };
    int n = arr.Length;
    Console.WriteLine( xorPairSum(arr, n));
}
}
 
// This code is contributed
// by Arnab Kundu

<?php
// PHP program to find
// XOR of pair sums.
 
function xor_pair_sum($ar, $n)
{
    $total = 0;
    for($i = 0; $i < $n; $i++)
        $total = $total ^ $ar[$i];
 
    return (2 * $total);
}
 
// Driver Code
$data = array(1, 2, 3);
$n = sizeof($data);
echo xor_pair_sum($data, $n);
 
// This code is contributed
// by mits
?>

<script>
 
// Javascript program to find
// XOR of pair sums.
  
     
function xorPairSum(ar, n)
{
    var sum = 0;
    for (i = 0; i < n; i++)
    sum = sum ^ ar[i];
    return 2 * sum;
}
 
// Driver code
 
var arr = [ 1, 2, 3 ];
var n = arr.length;
document.write( xorPairSum(arr, n));
 
 
// This code is contributed by Amit Katiyar
 
</script>

0

Complejidad de tiempo : O(N)