Given an array A of size n. the task is to generate a new sequence B with size N^2 having elements sum of every pair of array A and find the xor value of the sum of all the pairs formed.
Note: Here (A[i], A[i]), (A[i], A[j]), (A[j], A[i]) all are considered as different pairs.
Examples:
Input: arr[] = {1, 5, 6}
Output: 4
B[3*3] = { 1+1, 1+5, 1+6, 5+1, 5+5, 5+6, 6+1, 6+5, 6+6}
B[9] = { 2, 6, 7, 6, 10, 11, 7, 11, 12}
So, 2 ^ 6 ^ 7 ^ 6 ^ 10 ^ 11 ^ 7 ^ 6 ^ 11 ^ 12 = 4
Input arr[]:{1, 2}
Output :6
A Naive approach is to run two loops. Consider each and every pair, take their sum, and calculate the xor value of the sum of all the pairs.
An Efficient approach is based upon the fact that xor of the same values is 0.
All the pairs like (a[i], a[j]) and (a[j], a[i]) will have same sum. So, their xor values will be 0. Only the pairs like (a[i], a[i]) will give the different result. So, take the xor of all the elements of the given array and multiply it by 2.
Implementation:
C++
// C++ program to find XOR of// sum of every possible pairs// in an array#include <bits/stdc++.h>using namespace std;// Function to find XOR of sum// of all pairsint findXor(int arr[], int n){ // Calculate xor of all the elements int xoR = 0; for (int i = 0; i < n; i++) { xoR = xoR ^ arr[i]; } // Return twice of xor value return xoR * 2;}// Drivers codeint main(){ int arr[3] = { 1, 5, 6 }; int n = sizeof(arr) / sizeof(arr[0]); cout << findXor(arr, n); return 0;} |
Java
// Java program to find XOR of// sum of every possible pairs// in an arrayimport java.io.*;class GFG { // Function to find XOR of sum // of all pairs static int findXor(int arr[], int n) { // Calculate xor of all the // elements int xoR = 0; for (int i = 0; i < n; i++) { xoR = xoR ^ arr[i]; } // Return twice of xor value return xoR * 2; } // Drivers code public static void main (String[] args) { int arr[] = { 1, 5, 6 }; int n = arr.length; System.out.println( findXor(arr, n)); }}// This code is contributed by anuj_67. |
Python3
# Python3 program to find # XOR of sum of every # possible pairs in an array# Function to find XOR # of sum of all pairsdef findXor(arr,n): # Calculate xor of # all the elements xoR = 0; for i in range (0, n ) : xoR = xoR ^ arr[i] # Return twice of # xor value return xoR * 2# Driver codearr = [ 1, 5, 6 ]n = len(arr)print(findXor(arr, n))# This code is contributed # by ihritik |
C#
// C# program to find XOR of// sum of every possible pairs// in an arrayusing System;class GFG { // Function to find XOR of sum // of all pairs static int findXor(int []arr, int n) { // Calculate xor of all the // elements int xoR = 0; for (int i = 0; i < n; i++) { xoR = xoR ^ arr[i]; } // Return twice of xor value return xoR * 2; } // Drivers code public static void Main () { int []arr = { 1, 5, 6 }; int n = arr.Length; Console.WriteLine( findXor(arr, n)); }}// This code is contributed by anuj_67. |
PHP
<?php// PHP program to find XOR// of sum of every possible // pairs in an array// Function to find XOR // of sum of all pairsfunction findXor($arr, $n){ // Calculate xor of // all the elements $xoR = 0; for ($i = 0; $i < $n; $i++) { $xoR = $xoR ^ $arr[$i]; } // Return twice // of xor value return $xoR * 2;}// Driver code$arr = array(1, 5, 6);$n = count($arr);echo findXor($arr, $n);// This code is contributed// by anuj_67.?> |
Javascript
<script>// Javascript program to find XOR of// sum of every possible pairs// in an array// Function to find XOR of sum// of all pairsfunction findXor(arr, n){ // Calculate xor of all the elements let xoR = 0; for (let i = 0; i < n; i++) { xoR = xoR ^ arr[i]; } // Return twice of xor value return xoR * 2;}// Drivers code let arr = [ 1, 5, 6 ]; let n = arr.length; document.write(findXor(arr, n)); </script> |
Output
4
Complexity Analysis:
- Time Complexity: O(n)
- Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
