HackerRank Maximum Xor problem solution

In this HackerRank Maximum Xor Interview preparation kit problem solution, you are given an array arr of n elements. A list of integer queries is given as input, and find the maximum value of queries[j].

Function Description

Complete the maxXor function in the editor below. It must return an array of integers, each representing the maximum xor value for each element queries[j] against all elements of arr.

maxXor has the following parameter(s):

• arr: an array of integers
• queries: an array of integers to query

HackerRank Maximum Xor problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the maxXor function below.
def maxXor(arr, queries):
    ans = []
    trie = {}
    k = len(bin(max(arr+queries))) - 2 
    for number in ['{:b}'.format(x).zfill(k) for x in arr]:
        node = trie
        for char in number:
            node = node.setdefault(char, {})
    for n in queries:
        node = trie
        s = ''
        for char in'{:b}'.format(n).zfill(k) :
            tmp = str(int(char) ^ 1) 
            tmp = tmp if tmp in node else char 
            s += tmp 
            node = node[tmp]
        ans.append(int(s, 2) ^ n) 
    return ans

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    arr = list(map(int, input().rstrip().split()))

    m = int(input())

    queries = []

    for _ in range(m):
        queries_item = int(input())
        queries.append(queries_item)

    result = maxXor(arr, queries)

    fptr.write('n'.join(map(str, result)))
    fptr.write('n')

    fptr.close()

Maximum Xor problem solution in C++.

#include <bits/stdc++.h>
using namespace std;

int p;
struct node
{
    int val;
    node *child[2];
};

void insert(node *trie, int x, int ind)
{   
    if(ind < 0) {
        return;
    }
    int k=(x>>ind)&1;

    if(!trie->child[k]) {
        trie->child[k]=new node;
    }
    insert(trie->child[k], x, ind-1);
}

void find(node *trie, int x, int ind)
{   
    if(ind<0) {
        return;
    }

    int k=(x>>ind)&1;
    k^=1;

    if(!trie->child[k]) {
        k^=1;
    }
    p=p<<1|k;
    find(trie->child[k], x, ind-1);
}

int main()
{
    int n,i,x;
    cin>>n;

    int a[n];
    for(i=0;i<n;++i) {
        cin>>a[i];
    }

    node *trie = new node;
    for(i=0;i<n;++i) {
        // max 32 bits
        insert(trie,a[i],31);
    }

    int t;
    cin>>t;
    while(t--) {
        cin>>x;
        p=0;
        find(trie,x,31);
        cout<<(p^x)<<endl;
    }

    return 0;
}