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) { node.indices.add(idx); } 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 { BufferedReader br; StringTokenizer st; Scanner() { br = new BufferedReader(new InputStreamReader(System.in)); } Scanner(String fileName) throws FileNotFoundException { br = new BufferedReader(new FileReader(fileName)); } String next() throws IOException { while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine()); return st.nextToken(); } String nextLine() throws IOException { return br.readLine(); } 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()); } boolean ready() throws IOException { return br.ready(); } } 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> struct header { int* head; 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; struct header* info; 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; info = (struct header*)malloc(sizeof(struct header) * 65535); 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].head = table; 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; info[1].head = table + N; info[2].head = info[1].head + low; low = 0; hlow = 0; low_ind = 0; high_ind = 0; for (i = 0; i < N; ++i) { if ((table[i] & bit) == 0) { info[1].head[low_ind++] = i; if ((table[i] & next_bit) == 0) ++low; } else { info[2].head[high_ind++] = i; 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; info[child_low].head = info[child_low - 1].head + info[child_low - 1].count; info[child_high].head = info[child_low].head + info[child_low].count; 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) { info[child_low].head[low_ind++] = info[parent].head[j]; if ((table[info[parent].head[j]] & next_bit) == 0) ++low; } else { info[child_high].head[high_ind++] = info[parent].head[j]; 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("%dn", a ^ table[j]); } } free(table); free(info); return 0; }