Two arrays A and B consisting of N elements are given. The task is to compute the maximum possible XOR of every element in array A with array B.
Examples:
Input : A : 7 3 9 12 B : 1 3 5 2 Output : 6 6 12 15 Explanation : 1 xor 7 = 6, 5 xor 3 = 6, 5 xor 9 = 12, 3 xor 12 = 15.
A naive approach to solve this problem would be to check every element of array A with every other element of array B and print the maximum xor.
C++
// C++ code to find the maximum possible X-OR of // every array element with another array #include<bits/stdc++.h> using namespace std; int max_xor(int A[],int B[],int N) { // Variable to store the maximum xor int maximum; // Traversing for every element of // first array for(int i=0;i<N;i++) { maximum=INT_MIN; for(int j=0;j<N;j++) { maximum=max(maximum,A[i]^B[j]); } cout<<maximum<<endl; } } // Driver code int main() { int A[] = {7, 3, 9, 12}; int B[] = {1, 3, 5, 2}; int N = sizeof(A)/sizeof(A[0]); max_xor(A, B, N); return 0; } // This code is contributed by Utkarsh Kumar. |
Java
// Java code to find the maximum possible X-OR of // every array element with another array import java.io.*; class GFG { static void max_xor(int A[],int B[],int N) { // Variable to store the maximum xor int maximum; // Traversing for every element of // first array for(int i=0;i<N;i++) { maximum=Integer.MIN_VALUE; for(int j=0;j<N;j++) { maximum=Math.max(maximum,A[i]^B[j]); } System.out.println(maximum); } } // Driver code public static void main (String[] args) { int A[] = {7, 3, 9, 12}; int B[] = {1, 3, 5, 2}; int N = A.length; max_xor(A, B, N); } } // This code is contributed by Vaibhav |
Python3
# Python code to find the maximum possible X-OR of # every array element with another array def max_xor(A, B, N): # Variable to store the maximum xor maximum = -float('inf') # Traversing for every element of first array for i in range(N): maximum = -float('inf') for j in range(N): maximum = max(maximum, A[i] ^ B[j]) print(maximum) # Driver code if __name__ == '__main__': A = [7, 3, 9, 12] B = [1, 3, 5, 2] N = len(A) max_xor(A, B, N) |
C#
// C# code to find the maximum possible X-OR of // every array element with another array using System; class Program { static int MaxXOR(int[] A, int[] B, int N) { // Variable to store the maximum xor int maximum; // Traversing for every element of // first array for (int i = 0; i < N; i++) { maximum = int.MinValue; for (int j = 0; j < N; j++) { maximum = Math.Max(maximum, A[i] ^ B[j]); } Console.WriteLine(maximum); } return 0; } // Driver code static void Main() { int[] A = { 7, 3, 9, 12 }; int[] B = { 1, 3, 5, 2 }; int N = A.Length; MaxXOR(A, B, N); } } // This code is contributed by sarojmcy2e |
Javascript
// Function to find the maximum possible XOR of every element in array A with another element in array B function max_xor(A, B) { // Variable to store the maximum xor let maximum; // Traversing for every element of first array for (let i = 0; i < A.length; i++) { maximum = Number.MIN_SAFE_INTEGER; for (let j = 0; j < B.length; j++) { maximum = Math.max(maximum, A[i] ^ B[j]); } console.log(maximum); } } // Example usage let A = [7, 3, 9, 12]; let B = [1, 3, 5, 2]; max_xor(A, B); |
Output
6 6 12 15
Time Complexity : O(n^2)
Space Complexity : O(1)
An efficient solution is to use Trie Data Structure.
We maintain a Trie for the binary representation of all elements in array B. Now, for every element of A, we find the maximum xor in trie. Let's say our number A[i] is {b1, b2...bn}, where b1, b2...bn are binary bits. We start from b1. Now for the xor to be maximum, we'll try to make most significant bit 1 after performing the xor. So, if b1 is 0, we'll need a 1 and vice versa. In the trie, we go to the required bit side. If favourable option is not there, we'll go other side. Doing this all over, we'll get the maximum XOR possible.
Below is the implementation
C++
// C++ code to find the maximum possible X-OR of // every array element with another array #include<bits/stdc++.h> using namespace std; // Structure of Trie DS struct trie { int value; trie *child[2]; }; // Function to initialise a Trie Node trie * get() { trie * root = new trie; root -> value = 0; root -> child[0] = NULL; root -> child[1] = NULL; return root; } // Computing max xor int max_xor(trie * root, int key) { trie * temp = root; // Checking for all bits in integer range for (int i = 31; i >= 0; i--) { // Current bit in the number bool current_bit = ( key & ( 1 << i) ); // Traversing Trie for different bit, if found if (temp -> child[1 - current_bit] != NULL) temp = temp -> child[1 - current_bit]; // Traversing Trie for same bit else temp = temp -> child[current_bit]; } // Returning xor value of maximum bit difference // value. Thus, we get maximum xor value return (key ^ temp -> value); } // Inserting B[] in Trie void insert(trie * root, int key) { trie * temp = root; // Storing 31 bits as integer representation for (int i = 31; i >= 0; i--) { // Current bit in the number bool current_bit = key & (1 << i); // New node required if (temp -> child[current_bit] == NULL) temp -> child[current_bit] = get(); // Traversing in Trie temp = temp -> child[current_bit]; } // Assigning value to the leaf Node temp -> value = key; } int main() { int A[] = {7, 3, 9, 12}; int B[] = {1, 3, 5, 2}; int N = sizeof(A)/sizeof(A[0]); // Forming Trie for B[] trie * root = get(); for (int i = 0; i < N; i++) insert(root, B[i]); for (int i = 0; i < N; i++) cout << max_xor(root, A[i]) << endl; return 0; } |
Java
// Java code to find the maximum possible X-OR of // every array element with another array import java.util.*; class GFG { // Structure of Trie DS static class trie { int value; trie []child = new trie[2]; }; // Function to initialise a Trie Node static trie get() { trie root = new trie(); root.value = 0; root.child[0] = null; root.child[1] = null; return root; } // Computing max xor static int max_xor(trie root, int key) { trie temp = root; // Checking for all bits in integer range for (int i = 31; i >= 0; i--) { // Current bit in the number int current_bit = (key & (1 << i)); if(current_bit > 0) current_bit = 1; // Traversing Trie for different bit, if found if (temp.child[1 - current_bit] != null) temp = temp.child[1 - current_bit]; // Traversing Trie for same bit else temp = temp.child[current_bit]; } // Returning xor value of maximum bit difference // value. Thus, we get maximum xor value return (key ^ temp.value); } // Inserting B[] in Trie static void insert(trie root, int key) { trie temp = root; // Storing 31 bits as integer representation for (int i = 31; i >= 0; i--) { // Current bit in the number int current_bit = key & (1 << i); if(current_bit > 0) current_bit = 1; //System.out.println(current_bit); // New node required if (temp.child[current_bit] == null) temp.child[current_bit] = get(); // Traversing in Trie temp = temp.child[current_bit]; } // Assigning value to the leaf Node temp.value = key; } // Driver Code public static void main(String[] args) { int A[] = {7, 3, 9, 12}; int B[] = {1, 3, 5, 2}; int N = A.length; // Forming Trie for B[] trie root = get(); for (int i = 0; i < N; i++) insert(root, B[i]); for (int i = 0; i < N; i++) System.out.println(max_xor(root, A[i])); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 code to find the maximum # possible X-OR of every array # element with another array # Structure of Trie DS class trie: def __init__(self, value: int = 0) -> None: self.value = value self.child = [None] * 2 # Function to initialise a Trie Node def get() -> trie: root = trie() root.value = 0 root.child[0] = None root.child[1] = None return root # Computing max xor def max_xor(root: trie, key: int) -> int: temp = root # Checking for all bits in integer range for i in range(31, -1, -1): # Current bit in the number current_bit = (key & (1 << i)) if (current_bit > 0): current_bit = 1 # Traversing Trie for different bit, if found if (temp.child[1 - current_bit] != None): temp = temp.child[1 - current_bit] # Traversing Trie for same bit else: temp = temp.child[current_bit] # Returning xor value of maximum bit difference # value. Thus, we get maximum xor value return (key ^ temp.value) # Inserting B[] in Trie def insert(root: trie, key: int) -> None: temp = root # Storing 31 bits as integer representation for i in range(31, -1, -1): # Current bit in the number current_bit = key & (1 << i) if (current_bit > 0): current_bit = 1 # New node required if (temp.child[current_bit] == None): temp.child[current_bit] = get() # Traversing in Trie temp = temp.child[current_bit] # Assigning value to the leaf Node temp.value = key # Driver Code if __name__ == "__main__": A = [ 7, 3, 9, 12 ] B = [ 1, 3, 5, 2 ] N = len(A) # Forming Trie for B[] root = get() for i in range(N): insert(root, B[i]) for i in range(N): print(max_xor(root, A[i])) # This code is contributed by sanjeev2552 |
C#
// C# code to find the maximum possible X-OR of // every array element with another array using System; class GFG { // Structure of Trie DS class trie { public int value; public trie []child = new trie[2]; }; // Function to initialise a Trie Node static trie get() { trie root = new trie(); root.value = 0; root.child[0] = null; root.child[1] = null; return root; } // Computing max xor static int max_xor(trie root, int key) { trie temp = root; // Checking for all bits in integer range for (int i = 31; i >= 0; i--) { // Current bit in the number int current_bit = (key & (1 << i)); if(current_bit > 0) current_bit = 1; // Traversing Trie for different bit, if found if (temp.child[1 - current_bit] != null) temp = temp.child[1 - current_bit]; // Traversing Trie for same bit else temp = temp.child[current_bit]; } // Returning xor value of maximum bit difference // value. Thus, we get maximum xor value return (key ^ temp.value); } // Inserting B[] in Trie static void insert(trie root, int key) { trie temp = root; // Storing 31 bits as integer representation for (int i = 31; i >= 0; i--) { // Current bit in the number int current_bit = key & (1 << i); if(current_bit > 0) current_bit = 1; // System.out.println(current_bit); // New node required if (temp.child[current_bit] == null) temp.child[current_bit] = get(); // Traversing in Trie temp = temp.child[current_bit]; } // Assigning value to the leaf Node temp.value = key; } // Driver Code public static void Main(String[] args) { int []A = {7, 3, 9, 12}; int []B = {1, 3, 5, 2}; int N = A.Length; // Forming Trie for B[] trie root = get(); for (int i = 0; i < N; i++) insert(root, B[i]); for (int i = 0; i < N; i++) Console.WriteLine(max_xor(root, A[i])); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code to find the maximum possible X-OR of // every array element with another array // Structure of Trie DS class trie { constructor() { this.value=0; this.child = new Array(2); } } // Function to initialise a Trie Node function get() { let root = new trie(); root.value = 0; root.child[0] = null; root.child[1] = null; return root; } // Computing max xor function max_xor(root,key) { let temp = root; // Checking for all bits in integer range for (let i = 31; i >= 0; i--) { // Current bit in the number let current_bit = (key & (1 << i)); if(current_bit > 0) current_bit = 1; // Traversing Trie for different bit, if found if (temp.child[1 - current_bit] != null) temp = temp.child[1 - current_bit]; // Traversing Trie for same bit else temp = temp.child[current_bit]; } // Returning xor value of maximum bit difference // value. Thus, we get maximum xor value return (key ^ temp.value); } // Inserting B[] in Trie function insert(root,key) { let temp = root; // Storing 31 bits as integer representation for (let i = 31; i >= 0; i--) { // Current bit in the number let current_bit = key & (1 << i); if(current_bit > 0) current_bit = 1; //System.out.println(current_bit); // New node required if (temp.child[current_bit] == null) temp.child[current_bit] = get(); // Traversing in Trie temp = temp.child[current_bit]; } // Assigning value to the leaf Node temp.value = key; } // Driver Code let A=[7, 3, 9, 12]; let B=[1, 3, 5, 2]; let N = A.length; // Forming Trie for B[] let root = get(); for (let i = 0; i < N; i++) insert(root, B[i]); for (let i = 0; i < N; i++) document.write(max_xor(root, A[i])+"<br>"); // This code is contributed by rag2127 </script> |
Output
6 6 12 15
Trie formation : O(N x MAX_BITS) where MAX_BITS is maximum number of bits in binary representation of numbers.
Calculating max bit difference : O(N x MAX_BITS)
Time Complexity : O(N x MAX_BITS)
This article is contributed by Rohit Thapliyal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
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!
