In this HackerRank Maximum Xor Interview preparation kit problem You are given an array arr of n elements. A list of integers queries is given as an input, find the maximum value of queries[j].
Problem solution in Python programming.
#!/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()
Problem solution in C++ programming.
#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; }