Given two arrays A[] and B[] of equal length, the task is to find the Bitwise XOR of the pairwise sum of the given two arrays.
Examples:
Input: A[] = {1, 2}, B[] = {3, 4}
Output: 2
Explanation:
Sum of all possible pairs are {4(1 + 3), 5(1 + 4), 5(2 + 3), 6(2 + 4)}
XOR of all the pair sums = 4 ^ 5 ^ 5 ^ 6 = 2Input: A[] = {4, 6, 0, 0, 3, 3}, B[] = {0, 5, 6, 5, 0, 3}
Output: 8
Naive Approach: The simplest approach to solve the problem is to generate all possible pairs from the two given arrays and calculate their respective sums and update XOR with the sum of pairs. Finally, print the XOR obtained.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the sum of// XOR of the sum of every pairint XorSum(int A[], int B[], int N){ // Stores the XOR of sums // of every pair int ans = 0; // Iterate to generate all possible pairs for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // Update XOR ans = ans ^ (A[i] + B[j]); } } // Return the answer return ans;}// Driver Codeint main(){ int A[] = { 4, 6, 0, 0, 3, 3 }; int B[] = { 0, 5, 6, 5, 0, 3 }; int N = sizeof A / sizeof A[0]; cout << XorSum(A, B, N) << endl; return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG{// Function to calculate the sum of// XOR of the sum of every pairstatic int XorSum(int A[], int B[], int N){ // Stores the XOR of sums // of every pair int ans = 0; // Iterate to generate all possible pairs for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { // Update XOR ans = ans ^ (A[i] + B[j]); } } // Return the answer return ans;}// Driver Codepublic static void main (String[] args) { int A[] = { 4, 6, 0, 0, 3, 3 }; int B[] = { 0, 5, 6, 5, 0, 3 }; int N = A.length; System.out.println(XorSum(A, B, N));}}// This code is contributed by AnkitRai01 |
Python3
# Python3 program to implement# the above approach# Function to calculate the sum of# XOR of the sum of every pairdef XorSum(A, B, N): # Stores the XOR of sums # of every pair ans = 0 # Iterate to generate all # possible pairs for i in range(N): for j in range(N): # Update XOR ans = ans ^ (A[i] + B[j]) # Return the answer return ans# Driver Codeif __name__ == "__main__": A = [ 4, 6, 0, 0, 3, 3 ] B = [ 0, 5, 6, 5, 0, 3 ] N = len(A) print (XorSum(A, B, N))# This code is contributed by chitranayal |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to calculate the sum of// XOR of the sum of every pairstatic int XorSum(int []A, int []B, int N){ // Stores the XOR of sums // of every pair int ans = 0; // Iterate to generate all possible pairs for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { // Update XOR ans = ans ^ (A[i] + B[j]); } } // Return the answer return ans;}// Driver Codepublic static void Main(String[] args) { int []A = {4, 6, 0, 0, 3, 3}; int []B = {0, 5, 6, 5, 0, 3}; int N = A.Length; Console.WriteLine(XorSum(A, B, N));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript program to implement// the above approach // Function to calculate the sum of // XOR of the sum of every pair function XorSum(A , B , N) { // Stores the XOR of sums // of every pair var ans = 0; // Iterate to generate all possible pairs for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { // Update XOR ans = ans ^ (A[i] + B[j]); } } // Return the answer return ans; } // Driver Code var A = [ 4, 6, 0, 0, 3, 3 ]; var B = [ 0, 5, 6, 5, 0, 3 ]; var N = A.length; document.write(XorSum(A, B, N));// This code contributed by umadevi9616 </script> |
Output:
8
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using the Bit Manipulation technique. Follow the steps below to solve the problem:
- Considering only the Kth bit, the task is to count the number of pairs (i, j) such that the Kth bit of (Ai + Bj) is set.
- If this number is odd, add X = 2k to the answer. We are only interested in the values of (ai, bj) in modulo 2X.
- Thus, replace ai with ai % (2X) and bj with bj % (2X), and assume that ai and bj < 2X.
- There are two cases when the kth bit of (ai + bj) is set:
- x ? ai + bj < 2x
- 3x ? ai + bj < 4x
- Hence, sort b[] in increasing order. For a fixed i, the set of j that satisfies X ? (ai +bj) < 2X forms an interval.
- Therefore, count the number of such j by Binary search. Similarly, handle the second case.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the// XOR of the sum of every pairint XorSum(int A[], int B[], int N){ // Stores the maximum bit const int maxBit = 29; int ans = 0; // Look for all the k-th bit for (int k = 0; k < maxBit; k++) { // Stores the modulo of // elements B[] with (2^(k+1)) int C[N]; for (int i = 0; i < N; i++) { // Calculate modulo of // array B[] with (2^(k+1)) C[i] = B[i] % (1 << (k + 1)); } // Sort the array C[] sort(C, C + N); // Stores the total number // whose k-th bit is set long long count = 0; long long l, r; for (int i = 0; i < N; i++) { // Calculate and store the modulo // of array A[] with (2^(k+1)) int x = A[i] % (1 << (k + 1)); // Lower bound to count the number // of elements having k-th bit in // the range (2^k - x, 2* 2^(k) - x) l = lower_bound(C, C + N, (1 << k) - x) - C; r = lower_bound(C, C + N, (1 << k) * 2 - x) - C; // Add total number i.e (r - l) // whose k-th bit is one count += (r - l); // Lower bound to count the number // of elements having k-th bit in // range (3 * 2^k - x, 4*2^(k) - x) l = lower_bound(C, C + N, (1 << k) * 3 - x) - C; r = lower_bound(C, C + N, (1 << k) * 4 - x) - C; count += (r - l); } // If count is even, Xor of // k-th bit becomes zero, no // need to add to the answer. // If count is odd, only then, // add to the final answer if (count & 1) ans += (1 << k); } // Return answer return ans;}// Driver codeint main(){ int A[] = { 4, 6, 0, 0, 3, 3 }; int B[] = { 0, 5, 6, 5, 0, 3 }; int N = sizeof A / sizeof A[0]; // Function call cout << XorSum(A, B, N) << endl; return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{ // Lower boundstatic int lower_bound(int[] a, int low, int high, int element){ while(low < high) { int middle = low + (high - low) / 2; if(element > a[middle]) low = middle + 1; else high = middle; } return low;}// Function to calculate the// XOR of the sum of every pairstatic int XorSum(int A[], int B[], int N){ // Stores the maximum bit final int maxBit = 29; int ans = 0; // Look for all the k-th bit for (int k = 0; k < maxBit; k++) { // Stores the modulo of // elements B[] with (2^(k+1)) int []C = new int[N]; for (int i = 0; i < N; i++) { // Calculate modulo of // array B[] with (2^(k+1)) C[i] = B[i] % (1 << (k + 1)); } // Sort the array C[] Arrays.sort(C); // Stores the total number // whose k-th bit is set long count = 0; long l, r; for (int i = 0; i < N; i++) { // Calculate and store the modulo // of array A[] with (2^(k+1)) int x = A[i] % (1 << (k + 1)); // Lower bound to count // the number of elements // having k-th bit in // the range (2^k - x, // 2* 2^(k) - x) l = lower_bound(C, 0, N, (1 << k) - x); r = lower_bound(C, 0, N, (1 << k) * 2 - x); // Add total number i.e // (r - l) whose k-th bit is one count += (r - l); // Lower bound to count // the number of elements // having k-th bit in // range (3 * 2^k - x, // 4*2^(k) - x) l = lower_bound(C, 0, N, (1 << k) * 3 - x); r = lower_bound(C, 0, N, (1 << k) * 4 - x); count += (r - l); } // If count is even, Xor of // k-th bit becomes zero, no // need to add to the answer. // If count is odd, only then, // add to the final answer if ((count & 1) != 0) ans += (1 << k);}// Return answerreturn ans;}// Driver codepublic static void main(String[] args){ int A[] = {4, 6, 0, 0, 3, 3}; int B[] = {0, 5, 6, 5, 0, 3}; int N = A.length; // Function call System.out.print(XorSum(A, B, N) + "\n");}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program to implement# the above approachfrom bisect import bisect, bisect_left, bisect_right# Function to calculate the# XOR of the sum of every pairdef XorSum(A, B, N): # Stores the maximum bit maxBit = 29 ans = 0 # Look for all the k-th bit for k in range(maxBit): # Stores the modulo of # elements B[] with (2^(k+1)) C = [0] * N for i in range(N): # Calculate modulo of # array B[] with (2^(k+1)) C[i] = B[i] % (1 << (k + 1)) # Sort the array C[] C = sorted(C) # Stores the total number # whose k-th bit is set count = 0 l, r = 0, 0 for i in range(N): # Calculate and store the modulo # of array A[] with (2^(k+1)) x = A[i] % (1 << (k + 1)) # Lower bound to count the number # of elements having k-th bit in # the range (2^k - x, 2* 2^(k) - x) l = bisect_left(C, (1 << k) - x) r = bisect_left(C, (1 << k) * 2 - x) # Add total number i.e (r - l) # whose k-th bit is one count += (r - l) # Lower bound to count the number # of elements having k-th bit in # range (3 * 2^k - x, 4*2^(k) - x) l = bisect_left(C, (1 << k) * 3 - x) r = bisect_left(C, (1 << k) * 4 - x) count += (r - l) # If count is even, Xor of # k-th bit becomes zero, no # need to add to the answer. # If count is odd, only then, # add to the final answer if (count & 1): ans += (1 << k) # Return answer return ans# Driver codeif __name__ == '__main__': A = [ 4, 6, 0, 0, 3, 3 ] B = [ 0, 5, 6, 5, 0, 3 ] N = len(A) # Function call print(XorSum(A, B, N))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG{// Lower boundstatic int lower_bound(int[] a, int low, int high, int element){ while (low < high) { int middle = low + (high - low) / 2; if (element > a[middle]) low = middle + 1; else high = middle; } return low;}// Function to calculate the// XOR of the sum of every pairstatic int XorSum(int[] A, int[] B, int N){ // Stores the maximum bit int maxBit = 29; int ans = 0; // Look for all the k-th bit for(int k = 0; k < maxBit; k++) { // Stores the modulo of // elements B[] with (2^(k+1)) int[] C = new int[N]; for(int i = 0; i < N; i++) { // Calculate modulo of // array B[] with (2^(k+1)) C[i] = B[i] % (1 << (k + 1)); } // Sort the array C[] Array.Sort(C); // Stores the total number // whose k-th bit is set long count = 0; long l, r; for(int i = 0; i < N; i++) { // Calculate and store the modulo // of array A[] with (2^(k+1)) int x = A[i] % (1 << (k + 1)); // Lower bound to count // the number of elements // having k-th bit in // the range (2^k - x, // 2* 2^(k) - x) l = lower_bound(C, 0, N, (1 << k) - x); r = lower_bound(C, 0, N, (1 << k) * 2 - x); // Add total number i.e // (r - l) whose k-th bit is one count += (r - l); // Lower bound to count // the number of elements // having k-th bit in // range (3 * 2^k - x, // 4*2^(k) - x) l = lower_bound(C, 0, N, (1 << k) * 3 - x); r = lower_bound(C, 0, N, (1 << k) * 4 - x); count += (r - l); } // If count is even, Xor of // k-th bit becomes zero, no // need to add to the answer. // If count is odd, only then, // add to the final answer if ((count & 1) != 0) ans += (1 << k); } // Return answer return ans;}// Driver codepublic static void Main(string[] args){ int[] A = { 4, 6, 0, 0, 3, 3 }; int[] B = { 0, 5, 6, 5, 0, 3 }; int N = A.Length; // Function call Console.Write(XorSum(A, B, N) + "\n");}}// This code is contributed by grand_master |
Javascript
<script>// Javascript Program to implement// the above approach// Lower boundfunction lower_bound(a,low,high,element){ while(low < high) { let middle = low + Math.floor((high - low) / 2); if(element > a[middle]) low = middle + 1; else high = middle; } return low;}// Function to calculate the// XOR of the sum of every pairfunction XorSum(A,B,N){ // Stores the maximum bit let maxBit = 29; let ans = 0; // Look for all the k-th bit for (let k = 0; k < maxBit; k++) { // Stores the modulo of // elements B[] with (2^(k+1)) let C = new Array(N); for (let i = 0; i < N; i++) { // Calculate modulo of // array B[] with (2^(k+1)) C[i] = B[i] % (1 << (k + 1)); } // Sort the array C[] C.sort(function(x,y){return x-y;}); // Stores the total number // whose k-th bit is set let count = 0; let l, r; for (let i = 0; i < N; i++) { // Calculate and store the modulo // of array A[] with (2^(k+1)) let x = A[i] % (1 << (k + 1)); // Lower bound to count // the number of elements // having k-th bit in // the range (2^k - x, // 2* 2^(k) - x) l = lower_bound(C, 0, N, (1 << k) - x); r = lower_bound(C, 0, N, (1 << k) * 2 - x); // Add total number i.e // (r - l) whose k-th bit is one count += (r - l); // Lower bound to count // the number of elements // having k-th bit in // range (3 * 2^k - x, // 4*2^(k) - x) l = lower_bound(C, 0, N, (1 << k) * 3 - x); r = lower_bound(C, 0, N, (1 << k) * 4 - x); count += (r - l); } // If count is even, Xor of // k-th bit becomes zero, no // need to add to the answer. // If count is odd, only then, // add to the final answer if ((count & 1) != 0) ans += (1 << k);} // Return answerreturn ans;}// Driver codelet A=[4, 6, 0, 0, 3, 3];let B=[0, 5, 6, 5, 0, 3];let N = A.length;// Function call document.write(XorSum(A, B, N) + "\n");// This code is contributed by avanitrachhadiya2155</script> |
Output:
8
Time Complexity: O(NlogN)
Auxiliary Space: O(N)
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!
