# HackerRank XOR key problem solution

In this HackerRank XOR key problem solution, Xorq invented an encryption algorithm that uses bitwise XOR operations extensively. This encryption algorithm uses a sequence of non-negative integers x = [x[1],x[2]....x[n]] as its key. To implement this algorithm efficiently, Xorq needs to find the maximum value of A XOR xj for given integers A, L, and R, such that, L <= j <= r. Help Xorq implement this function.

## Problem solution in Python.

```#!/bin/python3

import os
import sys

def xorKey(x, queries):
ans = []
bitset = [None]*(1 << 16)
for i in range(len(x)):
if bitset[x[i]]:
bitset[x[i]].append(i)
else:
bitset[x[i]] = [i]
m = max(x)
i = 0
while m > 0:
m >>= 1
i += 1
m = (1 << i) - 1
allset = ((1 << 16) - 1) & m

for q in queries:
ideal = q[0]^allset
for i in range(1 << 16):
if inrange(bitset[i^ideal], q):
ans.append(allset^i)
break
return ans

def inrange(a, q):
if a:
p = b_search(a, q[1]-1)
if p < len(a) and a[p] < q[2]:
return True
return False
return False

def b_search(a, x):
l = 0
r = len(a)
while l != r:
m = l + (r-l)//2
if x > a[m]:
l = m + 1
else:
r = m
return r

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

t = int(input())

for t_itr in range(t):
nq = input().split()

n = int(nq[0])

q = int(nq[1])

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

queries = []

for _ in range(q):
queries.append(list(map(int, input().rstrip().split())))

result = xorKey(x, queries)

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

fptr.close()```

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class B {

static int MAX = 15;

public static void main(String[] args) throws IOException {
Scanner sc = new Scanner();
PrintWriter out = new PrintWriter(System.out);
int tc = sc.nextInt();
while (tc-- > 0) {
int n = sc.nextInt(), q = sc.nextInt();
Trie trie = new Trie();
for (int i = 1; i <= n; i++) {
trie.insert(sc.nextInt(), i);
}
trie.sort();
while (q-- > 0) {
out.println(trie.query(sc.nextInt(), sc.nextInt(), sc.nextInt()));
}
}

out.close();

}

static class node {
ArrayList<Integer> indices;
node one, zero;

node() {
indices = new ArrayList();
}

void createChild(int t) {
if (t == 0) {
if (zero == null)
zero = new node();
} else if (one == null) {
one = new node();
}
}

boolean has(int l, int r) {
int lo = 0, hi = indices.size() - 1;
while (lo <= hi) {
int mid = lo + hi >> 1;
int curr = indices.get(mid);
if (curr < l) {
lo = mid + 1;
} else if (curr <= r)
return true;
else
hi = mid - 1;

}
return false;
}

void sort() {
Collections.sort(indices);
if (one != null)
one.sort();
if (zero != null)
zero.sort();
}
}

static class Trie {
node root;

Trie() {
root = new node();
}

void sort() {
root.sort();
}

void insert(int x, int idx) {
insert(x, root, idx, MAX);
}

void insert(int x, node node, int idx, int bit) {
if (node != root) {
}
if (bit == -1)
return;
int currBit = ((x & (1 << bit)) == 0) ? 0 : 1;
node.createChild(currBit);
insert(x, currBit == 0 ? node.zero : node.one, idx, bit - 1);

}

int query(int x, int l, int r) {
return query(x, l, r, root, MAX);
}

int query(int x, int l, int r, node node, int bit) {
if (bit == -1)
return 0;
int best = (x & 1 << bit) == 0 ? 1 : 0;
node child = best == 0 ? node.zero : node.one;
if (child != null && child.has(l, r)) {
return (1 << bit) + query(x, l, r, child, bit - 1);
} else {
return query(x, l, r, best == 0 ? node.one : node.zero, bit - 1);

}
}
}

static class Scanner {
StringTokenizer st;

Scanner() {
}

Scanner(String fileName) throws FileNotFoundException {
}

String next() throws IOException {
while (st == null || !st.hasMoreTokens())
return st.nextToken();
}

String nextLine() throws IOException {
}

int nextInt() throws IOException {
return Integer.parseInt(next());
}

long nextLong() throws NumberFormatException, IOException {
return Long.parseLong(next());
}

double nextDouble() throws NumberFormatException, IOException {
return Double.parseDouble(next());
}

}

}

static void sort(int[] a) {
shuffle(a);
Arrays.sort(a);
}

static void shuffle(int[] a) {
int n = a.length;
Random rand = new Random();
for (int i = 0; i < n; i++) {
int tmpIdx = rand.nextInt(n);
int tmp = a[i];
a[i] = a[tmpIdx];
a[tmpIdx] = tmp;
}
}

}```

## Problem solution in C++.

```#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
long T; cin>>T;
long Q,N;
unsigned long a,p,q;
const unsigned long dec=2048;
const unsigned long INT=32767;

for(long t=0;t<T;t++){
cin>>N>>Q;

unsigned long x[N+1];
unsigned long next[N+1][16];
vector<unsigned long> position[32768];

for(long n=1;n<=N;n++){
cin>>x[n];
position[x[n]].push_back(n);
}

for(long i=0;i<16;i++){
long p=0; q=1;
while(q<=N){
while(q<=N && (x[q]>>11)!=i ) q++;
while(p<q){
next[p][i]=q;
p++;
}
q++;
}
if(p==N) next[p][i]=N+1;
}

for(long s=0;s<Q;s++){
cin>>a>>p>>q;

if(q-p<=2000){
unsigned long m=0;
for(long i=p;i<=q;i++)
m=max(m,a^x[i]);
cout<<m<<endl;
}
else{
unsigned long test=INT;
while(next[p-1][(test^a)>>11]>q) test-=dec;

bool NotFound=true;
while(NotFound){
unsigned long match=test^a;
if(position[match].empty()) test--;
else{
long i=0;
while(i<position[match].size() && position[match][i]<p) i++;
if(i!=position[match].size()){
if(position[match][i]<=q){
NotFound=false;
}
else test--;
}
else test--;
}
}

cout<<test<<endl;
}
}

}
}        ```

## Problem solution in C.

```#define NDEBUG

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int count;
};

int find(const int* base, int count, int p, int q)
{
int left = 0;
int right = count;
int mid;
int r;

while (left < right) {
mid = (left + right) / 2;
r = base[mid];
if (r > q) {
right = mid;
} else if (r < p) {
left = mid + 1;
} else {
return r;
}
}

return -1;
}

int main(void)
{
int T, t;
int N, n;
int Q, r;
int a, p, q;

int* table;

int i, j;
int ret;
int bit;
int next_bit;
int low;
int hlow;
int parent;
int child_low;
int child_high;
int low_ind;
int high_ind;

assert(info != NULL);

table = (int*)malloc(sizeof(int) * 1600000);
assert(table != NULL);

ret = scanf("%d", &T);
assert(ret == 1);
assert(1 <= T && T <= 6);

for (t = 0; t < T; ++t) {
ret = scanf("%d%d", &N, &Q);
assert(ret == 2);
assert(1 <= N && N <= 100000);
assert(1 <= Q && Q <= 50000);

info[0].count = N;

low = 0;

for (n = 0; n < N; ++n) {
ret = scanf("%d", table + n);
assert(ret == 1);
assert(0 <= table[n] && table[n] < 0x8000);

if ((table[n] & 0x4000) == 0)
++low;
}
info[1].count = low;
info[2].count = N - low;

bit = 0x4000;
next_bit = bit >> 1;

low = 0;
hlow = 0;

low_ind = 0;
high_ind = 0;
for (i = 0; i < N; ++i) {
if ((table[i] & bit) == 0) {
if ((table[i] & next_bit) == 0)
++low;
} else {
if ((table[i] & next_bit) == 0)
++hlow;
}
}
assert(low_ind == info[1].count);
assert(high_ind == info[2].count);

info[3].count = low;
info[4].count = low_ind - low;
info[5].count = hlow;
info[6].count = high_ind - hlow;

parent = 0;
for (bit = next_bit; bit > 0; bit = next_bit) {
next_bit = bit >> 1;
for (i = 0; i < 0x4000; i += bit) {
++parent;
child_low = parent + parent + 1;
child_high = child_low + 1;

low = 0;
hlow = 0;

low_ind = 0;
high_ind = 0;
for (j = 0; j < info[parent].count; ++j) {
if ((table[info[parent].head[j]] & bit) == 0) {
if ((table[info[parent].head[j]] & next_bit) == 0)
++low;
} else {
if ((table[info[parent].head[j]] & next_bit) == 0)
++hlow;
}
}
assert(low_ind == info[child_low].count);
assert(high_ind == info[child_high].count);

if (next_bit > 0) {
j = child_low + child_low + 1;
info[j++].count = low;
info[j++].count = low_ind - low;
info[j++].count = hlow;
info[j++].count = high_ind - hlow;
}
}
}

for (r = 0; r < Q; ++r) {
ret = scanf("%d%d%d", &a, &p, &q);
assert(ret == 3);
assert(0 <= a && a < 0x8000);
assert(1 <= p && p <= q && q <= N);
--p;
--q;

i = 0;
for (bit = 0x4000; bit > 0; bit >>= 1) {
if ((a & bit) == 0) {
i = i + i + 2;
if (find(info[i].head, info[i].count, p, q) < 0)
--i;
} else {
i = i + i + 1;
if (find(info[i].head, info[i].count, p, q) < 0)
++i;
}
assert(find(info[i].head, info[i].count, p, q) >= 0);
}

j = find(info[i].head, info[i].count, p, q);
assert(j >= 0);
printf("%d\n", a ^ table[j]);
}
}

free(table);
free(info);

return 0;
}```