Given three arrays arr1[], arr2[], and arr3[] consisting of non-negative integers. The task is to find the bitwise XOR of the XOR of all possible triplets that are formed by taking one element from each array.
Examples:
Input: arr1[] = {2, 3, 1}, arr2[] = {2, 4}, arr3[] = {3, 5}
Output: 0
Explanation: All possible triplets are (2, 2, 3), (2, 2, 5), (2, 4, 3), (2, 4, 5), (3, 2, 3), (3, 2, 5), (3, 4, 3), (3, 4, 5), (1, 2, 3), (1, 2, 5), (1, 4, 3), (1, 4, 5). Bitwise XOR of all possible triplets are =(2^2^3) ^ (2^2^5) ^ (2^4^3) ^ (2^4^5) ^ (3^2^3) ^ (3^2^5) ^ (3^4^3) ^ (3^4^5) ^ (1^2^3) ^ (1^2^5) ^ (1^4^3) ^ (1^4^5) = 0Input: arr1[] = {1}, arr2[] = {3}, arr3[] = {4, 2, 3}
Output:7
Explanation: All possible triplets are (1, 3, 4), (1, 3, 2), (1, 3, 3)
Bitwise XOR of all possible triplets are = (1^3^4) ^ (1^3^2) ^ (1^3^3) =7
Naive Approach:
The basic idea is to traverse the arrays and generate all possible triplets from the given arrays. Finally, print the Bitwise XOR of each of these triplets from the given arrays.
Follow the steps below to solve the problem:
- Initialize a variable, say totalXOR, to store the bitwise XOR of each pair from these array sets.
- Traverse the given arrays and generate all possible triplets (arr[i], arr[j], arr[k]) from the given arrays.
- For each triplet arr[i], arr[j] and arr[k] update the value:
- totalXOR = (totalXOR ^ arr[i] ^ arr[j] ^ arr[k]).
- Finally, return the value of totalXOR.
Below is the Implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate xor value// of all tripletsint XorOfAllTriplets(int arr1[], int arr2[], int arr3[], int n1, int n2, int n3){ int result = 0; for (int i = 0; i < n1; i++) { for (int j = 0; j < n2; j++) { for (int k = 0; k < n3; k++) { result = result ^ (arr1[i] ^ arr2[j] ^ arr3[k]); } } } return result;}// Driver codeint main(){ int arr1[] = { 2, 3, 1 }; int arr2[] = { 2, 4 }; int arr3[] = { 3, 5 }; int n1 = sizeof(arr1) / sizeof(arr1[0]); int n2 = sizeof(arr2) / sizeof(arr2[0]); int n3 = sizeof(arr3) / sizeof(arr3[0]); // Function call cout << XorOfAllTriplets(arr1, arr2, arr3, n1, n2, n3); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to calculate xor value // of all triplets public static int XorOfAllTriplets(int arr1[], int arr2[], int arr3[], int n1, int n2, int n3) { int result = 0; for (int i = 0; i < n1; i++) { for (int j = 0; j < n2; j++) { for (int k = 0; k < n3; k++) { result = result ^ (arr1[i] ^ arr2[j] ^ arr3[k]); } } } return result; } // Driver Code public static void main(String[] args) { int arr1[] = { 2, 3, 1 }; int arr2[] = { 2, 4 }; int arr3[] = { 3, 5 }; int n1 = arr1.length; int n2 = arr2.length; int n3 = arr3.length; // Function call System.out.print( XorOfAllTriplets(arr1, arr2, arr3, n1, n2, n3)); }}// This code is contributed by Rohit Pradhan |
Python3
# Python code to implement the approach# Function to calculate xor value# of all tripletsdef XorOfAllTriplets(arr1, arr2, arr3, n1, n2, n3) : result = 0; for i in range(n1) : for j in range(n2) : for k in range(n3) : result = result ^ (arr1[i] ^ arr2[j] ^ arr3[k]); return result;# Driver codeif __name__ == "__main__" : arr1 = [ 2, 3, 1 ]; arr2 = [ 2, 4 ]; arr3 = [ 3, 5 ]; n1 = len(arr1); n2 = len(arr2); n3 = len(arr3); # Function call print(XorOfAllTriplets(arr1, arr2, arr3, n1, n2, n3)); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;public class GFG { // Function to calculate xor value // of all triplets public static int XorOfAllTriplets(int[] arr1, int[] arr2, int[] arr3, int n1, int n2, int n3) { int result = 0; for (int i = 0; i < n1; i++) { for (int j = 0; j < n2; j++) { for (int k = 0; k < n3; k++) { result = result ^ (arr1[i] ^ arr2[j] ^ arr3[k]); } } } return result; } static public void Main() { // Code int[] arr1 = { 2, 3, 1 }; int[] arr2 = { 2, 4 }; int[] arr3 = { 3, 5 }; int n1 = arr1.Length; int n2 = arr2.Length; int n3 = arr3.Length; // Function call Console.Write( XorOfAllTriplets(arr1, arr2, arr3, n1, n2, n3)); }}// This code is contributed by lokeshmvs21. |
Javascript
// Javascript code to implement the approach// Function to calculate xor value// of all tripletsfunction XorOfAllTriplets( arr1, arr2, arr3, n1,n2, in3){ let result = 0; for (let i = 0; i < n1; i++) { for (let j = 0; j < n2; j++) { for (let k = 0; k < n3; k++) { result = result ^ (arr1[i] ^ arr2[j] ^ arr3[k]); } } } return result;}// Driver code let arr1 = [ 2, 3, 1 ]; let arr2 = [ 2, 4 ]; let arr3 = [ 3, 5 ]; let n1 = arr1.length; let n2 = arr2.length; let n3 = arr3.length; // Function call console.log(XorOfAllTriplets(arr1, arr2, arr3, n1, n2, n3));// This code is contributed by garg28harsh. |
Output:
0
Time Complexity: O(N * M * P) where N, M and P are sizes of the three arrays
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, follow the observations below
Property of Bitwise XOR:
a ^ a ^ . . .( Even times ) = 0
a ^ a ^ a ^ . . .( Odd times ) = aSay the sizes of arr1[], arr2[] and arr3[] are N1, N2 and N3 respectively. Element of arr1[] occurs exactly N2 * N3 times. Similarly, arr2[] occurs exactly N3 * N1 and element of arr3[] occur exactly N1 * N2 times.
Follow the steps below to solve the problem:
- For each array check if the number of occurrences of its elements is odd or above using the above mentioned formula for occurrences:
- If the number of occurrences is odd, then XOR all the elements of that array with the final result.
- Otherwise, move to the next array.
- Return the final value of XOR.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate xor// value of all tripletsint XorOfAllTriplets(int arr1[], int arr2[], int arr3[], int n1, int n2, int n3){ int result = 0; // Checking if elements of arr1[] // will be present in final XOR if ((n2 * n3) % 2) for (int i = 0; i < n1; i++) result ^= arr1[i]; // Checking if elements of arr2[] // will be present in final XOR if ((n3 * n1) % 2) for (int j = 0; j < n2; j++) result ^= arr2[j]; // Checking if elements of arr3[] // will be present in final XOR if ((n1 * n2) % 2) for (int k = 0; k < n3; k++) result ^= arr3[k]; return result;}// Driver codeint main(){ int arr1[] = { 1 }; int arr2[] = { 3 }; int arr3[] = { 4, 2, 3 }; int N1 = sizeof(arr1) / sizeof(arr1[0]); int N2 = sizeof(arr2) / sizeof(arr2[0]); int N3 = sizeof(arr3) / sizeof(arr3[0]); // Function call cout << XorOfAllTriplets(arr1, arr2, arr3, N1, N2, N3); return 0;} |
Java
// Java code to implement the approachimport java.io.*; class GFG{// Function to calculate xor// value of all tripletspublic static int XorOfAllTriplets(int arr1[], int arr2[], int arr3[],int n1, int n2, int n3){ int result = 0; // Checking if elements of arr1[] // will be present in final XOR if ((n2 * n3) % 2==1) for (int i = 0; i < n1; i++) result ^= arr1[i]; // Checking if elements of arr2[] // will be present in final XOR if ((n3 * n1) % 2==1) for (int j = 0; j < n2; j++) result ^= arr2[j]; // Checking if elements of arr3[] // will be present in final XOR if ((n1 * n2) % 2==1) for (int k = 0; k < n3; k++) result ^= arr3[k]; return result;}// Driver codepublic static void main(String[] args){ int arr1[] = { 1 }; int arr2[] = { 3 }; int arr3[] = { 4, 2, 3 }; int N1 = arr1.length; int N2 = arr2.length; int N3 = arr3.length; // Function call System.out.println(XorOfAllTriplets(arr1, arr2, arr3, N1, N2, N3));}}// This code is contributed by Pushpesh Raj. |
Python3
# Python3 code to implement the approach# Function to calculate xor# value of all tripletsdef XorOfAllTriplets(arr1, arr2, arr3,n1, n2, n3) : result = 0; # Checking if elements of arr1[] # will be present in final XOR if ((n2 * n3) % 2) : for i in range(n1) : result ^= arr1[i]; # Checking if elements of arr2[] # will be present in final XOR if ((n3 * n1) % 2) : for j in range(n2) : result ^= arr2[j]; # Checking if elements of arr3[] # will be present in final XOR if ((n1 * n2) % 2) : for k in range(n3) : result ^= arr3[k]; return result;# Driver codeif __name__ == "__main__" : arr1 = [ 1 ]; arr2 = [ 3 ]; arr3 = [ 4, 2, 3 ]; N1 = len(arr1); N2 = len(arr2); N3 = len(arr3); # Function call print(XorOfAllTriplets(arr1, arr2, arr3, N1, N2, N3)); # This code is contributed by AnkThon |
C#
// C# code to implement the approachusing System;public class GFG{ // Function to calculate xor // value of all triplets public static int XorOfAllTriplets(int []arr1, int []arr2, int []arr3,int n1, int n2, int n3) { int result = 0; // Checking if elements of arr1[] // will be present in final XOR if ((n2 * n3) % 2==1) for (int i = 0; i < n1; i++) result ^= arr1[i]; // Checking if elements of arr2[] // will be present in final XOR if ((n3 * n1) % 2==1) for (int j = 0; j < n2; j++) result ^= arr2[j]; // Checking if elements of arr3[] // will be present in final XOR if ((n1 * n2) % 2==1) for (int k = 0; k < n3; k++) result ^= arr3[k]; return result; } // Driver code public static void Main(string[] args) { int []arr1 = { 1 }; int []arr2 = { 3 }; int []arr3 = { 4, 2, 3 }; int N1 = arr1.Length; int N2 = arr2.Length; int N3 = arr3.Length; // Function call Console.WriteLine(XorOfAllTriplets(arr1, arr2, arr3, N1, N2, N3)); }}// This code is contributed by AnkThon |
Javascript
// JavaScript code to implement the approach// Function to calculate xor// value of all tripletsfunction XorOfAllTriplets(arr1, arr2, arr3, n1, n2, n3){ var result = 0; // Checking if elements of arr1[] // will be present in final XOR if ((n2 * n3) % 2==1) for (let i = 0; i < n1; i++) result ^= arr1[i]; // Checking if elements of arr2[] // will be present in final XOR if ((n3 * n1) % 2==1) for (let j = 0; j < n2; j++) result ^= arr2[j]; // Checking if elements of arr3[] // will be present in final XOR if ((n1 * n2) % 2==1) for (let k = 0; k < n3; k++) result ^= arr3[k]; return result;}var arr1 = [ 1 ];var arr2 = [ 3 ];var arr3 = [ 4, 2, 3 ];var N1 = arr1.length;var N2 = arr2.length;var N3 = arr3.length;// Function callconsole.log(XorOfAllTriplets(arr1, arr2, arr3, N1, N2, N3));// This code is contributed by lokesh. |
Output
7
Time Complexity: O(N1 + N2 + N3)
Auxiliary Space: O(1)
