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) {
                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;
}