Maximum possible XOR of every element in an array with another array

Last Updated : 19 Sep, 2023

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

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

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)

XOR of every element of an Array with a given number K

GeeksforGeeks

Improve

Article Tags :

Practice Tags :

Maximum possible XOR of every element in an array with another array

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Similar Reads

Thank You!

What kind of Experience do you want to share?