XOR key – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include <iostream>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <ctime>
using namespace std;
const int MB = 14;
const int N = 100000;
int arr[N], t, n, q, a, b, c;
int sorted_arrs[N * (MB + 2)];
struct XorqNode {
int child[2], idx, len;
} nodes[512 + N * (MB - 6)]; //
int arr_cnt, node_cnt;
int split(int idx, int len, int bm, int r) {
int cnt = 0;
for(int i = 0; i < len; i ++) {
if((bm & arr[sorted_arrs[i + idx]]) == r) {
sorted_arrs[arr_cnt++] = sorted_arrs[i + idx];
cnt ++;
}
}
return cnt;
}
void build(int root, int idx, int len, int bit = MB) {
nodes[root].idx = idx;
nodes[root].len = len;
if(bit == -1) return;
int bm = (1 << bit);
int sidx1 = arr_cnt;
int left_cnt = split(idx, len, bm, 0);
int sidx2 = arr_cnt;
int right_cnt = split(idx, len, bm, bm);
assert(left_cnt + right_cnt == len);
if(left_cnt) {
nodes[root].child[0] = node_cnt;
build(node_cnt ++, sidx1, left_cnt, bit - 1);
} else {
nodes[root].child[0] = -1;
}
if(right_cnt) {
nodes[root].child[1] = node_cnt;
build(node_cnt ++, sidx2, right_cnt, bit - 1);
} else {
nodes[root].child[1] = -1;
}
}
bool search(int root, int from, int to) {
int left = nodes[root].idx;
int right = left + nodes[root].len - 1;
int r = N;
while(left <= right) {
int mid = (left + right) / 2;
int val = sorted_arrs[mid];
if(val >= from) {
r = val;
right = mid - 1;
} else {
left = mid + 1;
}
}
return r <= to;
}
int query(int root, int n, int from, int to, int bit = MB) {
if(bit == -1) return 0;
int mybit = ((1 << bit) & n) ? 1 : 0;
if(nodes[root].child[1 - mybit] != -1 && search(nodes[root].child[1 - mybit], from, to)) {
return query(nodes[root].child[1 - mybit], n, from, to, bit - 1) + (1 << bit);
} else {
return query(nodes[root].child[mybit], n, from, to, bit - 1);
}
}
int query2(int n, int from, int to) {
int r = 0;
for(int i = from; i <= to; i ++) {
r = max(r, arr[i] ^ n);
}
return r;
}
int main() {
int cl = clock();
int err_cnt = 0;
for(scanf("%d", &t); t--; ) {
arr_cnt = node_cnt = 0;
scanf("%d %d", &n, &q);
for(int i = 0; i < n; i ++) {
scanf("%d", &arr[i]);
}
for(int i = 0; i < n; i ++) {
sorted_arrs[arr_cnt++] = i;
}
node_cnt = 1;
build(0, 0, n);
for(int i = 0; i < q; i ++) {
scanf("%d %d %d", &a, &b, &c);
int r1 = query(0, a, b - 1, c - 1);
cout << r1 << endl;
}
}
//cerr << (clock() - cl) * 0.001 << endl;
return 0;
}
Java rep HackerRank Solution
import java.io.*;
import java.util.Random;
import java.util.StringTokenizer;
public class Solution implements Runnable {
// leave empty to read from stdin/stdout
private static final String TASK_NAME_FOR_IO = "";
// file names
private static final String FILE_IN = TASK_NAME_FOR_IO + ".in";
private static final String FILE_OUT = TASK_NAME_FOR_IO + ".out";
BufferedReader in;
PrintWriter out;
StringTokenizer tokenizer = new StringTokenizer("");
public static void main(String[] args) {
new Solution().run();
}
int n, tSize;
short[] a;
Tree[] md;
class Tree {
short[] p;
public Tree(short v) {
p = new short[] {v};
}
@SuppressWarnings({"ConstantConditions"})
public Tree(Tree l, Tree r) {
int cnt = (l != null ? l.p.length : 0) + (r != null ? r.p.length : 0);
p = new short[cnt];
int lIdx = 0;
int rIdx = 0;
for (int i = 0; i < cnt; i++) {
int lElem = (l != null && lIdx < l.p.length) ? l.p[lIdx] : Integer.MAX_VALUE;
int rElem = (r != null && rIdx < r.p.length) ? r.p[rIdx] : Integer.MAX_VALUE;
p[i] = (lElem < rElem) ? l.p[lIdx++] : r.p[rIdx++];
}
}
}
private void solve() throws IOException {
int tc = nextInt();
for (int tcIdx = 0; tcIdx < tc; tcIdx++) {
n = nextInt();
int m = nextInt();
a = new short[n];
for (int i = 0; i < n; i++) {
a[i] = (short) nextInt();
}
buildTree();
for (int i = 0; i < m; i++) {
int x = nextInt();
int l = nextInt() - 1;
int r = nextInt() - 1;
int answerFast = solveFast(x, l, r);
out.println(answerFast);
}
}
/*
for (int tcIdx = 0; tcIdx < 666; tcIdx++) {
stress();
}
*/
}
Random r = new Random(1234567789L);
private void stress() {
n = 1000;
a = new short[n];
int m = 50000;
for (int i = 0; i < n; i++) {
a[i] = (short) r.nextInt(1 << 15);
}
buildTree();
boolean failed = false;
for (int i = 0; i < m; i++) {
int x = r.nextInt(1 << 15);
int lo = r.nextInt(n / 100);
int hi = n / 100 + r.nextInt(n - n / 100);
// lo = 1;
// hi = 98302;
if (lo > hi) {
int t = lo; lo = hi; hi = t;
}
try {
int p1 = solveFast(x, lo, hi);
int p2 = solveNaive(x, lo, hi);
if (p1 != p2) {
throw new IllegalStateException(p1 + " vs. " + p2);
}
} catch (Exception e) {
e.printStackTrace();
System.err.println("1");
System.err.println(n + " " + 1);
for (int j = 0; j < n; j++) {
System.err.print(a[j] + " ");
}
System.err.println();
System.err.println(x + " " + lo + " " + hi);
System.err.flush();
failed = true;
break;
}
}
if (failed) {
throw new IllegalStateException("FAILED");
}
System.out.println("OK");
}
private void buildTree() {
tSize = 1;
while (tSize < n) {
tSize <<= 1;
}
// 1 2 3 4 5 6 7
// [tsize - 1] [tsize]
int alloc = tSize << 1;
md = new Tree[alloc];
build(1);
}
private void build(int pos) {
if (pos - tSize >= 0) {
if (pos - tSize < n) {
md[pos] = new Tree(a[pos - tSize]);
}
return;
}
int l = pos << 1;
int r = l + 1;
build(l);
build(r);
md[pos] = new Tree(md[l], md[r]);
}
int LOW_THRESHOLD = 1 << 6;
int foundSegmentsIdx;
Tree[] foundSegments = new Tree[1 << 10];
int[] ll = new int[1 << 10];
int[] rr = new int[1 << 10];
@SuppressWarnings({"ToArrayCallWithZeroLengthArrayArgument"})
private int solveFast(int x, int lo, int hi) {
// split [lo,hi] into segments with increasing length
foundSegmentsIdx = 0;
searchSegments(1, 0, tSize - 1, lo, hi);
// do not filter out anything, assign as is
int m = foundSegmentsIdx;
Tree[] segments = foundSegments;
// fill in left and right boundaries
for (int i = 0; i < m; i++) {
ll[i] = 0;
rr[i] = segments[i].p.length - 1;
}
// go through all bits and adjust
int answer = 0;
for (int bitIdx = 14; bitIdx >= 0; bitIdx--) {
int singleBitMask = 1 << bitIdx;
// find first and last element
int v1 = Integer.MAX_VALUE;
int v2 = Integer.MIN_VALUE;
int total = 0;
// next segments
int nextSegmentsIdx = 0;
for (int i = 0; i < m; i++) {
int length = rr[i] - ll[i] + 1;
// we shouldn't have any empty segments here
if (length <= 0) {
throw new IllegalStateException();
}
// calculate using a trivial approach for short segments
short[] v = segments[i].p;
if (length < LOW_THRESHOLD) {
for (int j = ll[i]; j <= rr[i]; j++) {
int t = x ^ v[j];
if (t > answer) {
answer = t;
}
}
continue;
}
// calculate min/max values
v1 = Math.min(v1, v[ll[i]]);
v2 = Math.max(v2, v[rr[i]]);
total += length;
if (i != nextSegmentsIdx) {
segments[nextSegmentsIdx] = segments[i];
ll[nextSegmentsIdx] = ll[i];
rr[nextSegmentsIdx] = rr[i];
}
nextSegmentsIdx++;
}
m = nextSegmentsIdx;
// shall we even proceed?
if (total <= 0) {
break;
}
// if the bits are equal, then we are just skipping the iteration as there is nothing to remove
if ((v1 & singleBitMask) == (v2 & singleBitMask)) {
continue;
}
// otherwise, there are elements that needs to be thrown away
if ((x & singleBitMask) == 0) {
// need to retain only ones
// [ ]
// 0 0 0 0 1 1 1 1
nextSegmentsIdx = 0;
for (int i = 0; i < m; i++)
if (ll[i] <= rr[i]) {
// the segment is not empty
short[] v = segments[i].p;
int L = ll[i];
int R = rr[i];
int bitL = v[L] & singleBitMask;
int bitR = v[R] & singleBitMask;
if (bitL == bitR) {
if (bitL != 0) {
// we have all one bits, and have to retain them
if (i != nextSegmentsIdx) {
segments[nextSegmentsIdx] = segments[i];
ll[nextSegmentsIdx] = ll[i];
rr[nextSegmentsIdx] = rr[i];
}
nextSegmentsIdx++;
}
continue;
}
// there is a median in the middle
while (L < R) {
int M = (L + R) >> 1;
if ((v[M] & singleBitMask) == 0) {
L = M + 1;
} else {
R = M;
}
}
/*
if ((v[L] & singleBitMask) == 0) {
throw new IllegalStateException("Median should point at the first non-zero");
}
if ((v[L - 1] & singleBitMask) != 0) {
throw new IllegalStateException("Incorrect median found");
}
*/
// we have to retain ones, so discard all ELEMENTS in CURRENT SEGMENT to the left
ll[i] = L;
if (i != nextSegmentsIdx) {
segments[nextSegmentsIdx] = segments[i];
ll[nextSegmentsIdx] = ll[i];
rr[nextSegmentsIdx] = rr[i];
}
nextSegmentsIdx++;
}
m = nextSegmentsIdx;
// end of a case where we are retaining ones
} else {
// need to retain only zeroes
// [ ]
// 0 0 0 0 1 1 1 1
nextSegmentsIdx = 0;
for (int i = 0; i < m; i++)
if (ll[i] <= rr[i]) {
// the segment is not empty
short[] v = segments[i].p;
int L = ll[i];
int R = rr[i];
int bitL = v[L] & singleBitMask;
int bitR = v[R] & singleBitMask;
if (bitL == bitR) {
if (bitL == 0) {
// we have all zero bits, and have to retain them
if (i != nextSegmentsIdx) {
segments[nextSegmentsIdx] = segments[i];
ll[nextSegmentsIdx] = ll[i];
rr[nextSegmentsIdx] = rr[i];
}
nextSegmentsIdx++;
}
continue;
}
// there is a median in the middle
while (L < R) {
int M = (L + R) >> 1;
if ((v[M] & singleBitMask) == 0) {
L = M + 1;
} else {
R = M;
}
}
/*
if ((v[L] & singleBitMask) == 0) {
throw new IllegalStateException("Median should point at the first non-zero");
}
if ((v[L - 1] & singleBitMask) != 0) {
throw new IllegalStateException("Incorrect median found");
}
*/
// we have to retain zeroes, so discard all ELEMENTS in CURRENT SEGMENT to the right
rr[i] = L - 1;
if (i != nextSegmentsIdx) {
segments[nextSegmentsIdx] = segments[i];
ll[nextSegmentsIdx] = ll[i];
rr[nextSegmentsIdx] = rr[i];
}
nextSegmentsIdx++;
}
m = nextSegmentsIdx;
} // end of a case where we are retaining zeroes
}
// see if there is still something left
for (int i = 0; i < m; i++)
if (ll[i] <= rr[i]) {
answer = Math.max(answer, x ^ segments[i].p[ll[i]]);
}
return answer;
}
private void searchSegments(int pos, int A, int B, int lo, int hi) {
if (hi < A || lo > B || A > B || lo > hi) {
return;
}
if (A == lo && B == hi) {
foundSegments[foundSegmentsIdx++] = md[pos];
return;
}
int posL = pos << 1;
int posR = posL + 1;
int mid = (A + B) / 2;
searchSegments(posL, A, mid, lo, Math.min(hi, mid));
searchSegments(posR, mid + 1, B, Math.max(lo, mid + 1), hi);
}
private int solveNaive(int x, int l, int r) {
int result = 0;
for (int i = l; i <= r; i++) {
result = Math.max(result, x ^ a[i]);
}
return result;
}
public void run() {
long timeStart = System.currentTimeMillis();
boolean fileIO = TASK_NAME_FOR_IO.length() > 0;
try {
if (fileIO) {
in = new BufferedReader(new FileReader(FILE_IN));
out = new PrintWriter(new FileWriter(FILE_OUT));
} else {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(new OutputStreamWriter(System.out));
}
solve();
in.close();
out.close();
} catch (IOException e) {
throw new IllegalStateException(e);
}
long timeEnd = System.currentTimeMillis();
if (fileIO) {
System.out.println("Time spent: " + (timeEnd - timeStart) + " ms");
}
}
private String nextToken() throws IOException {
while (!tokenizer.hasMoreTokens()) {
String line = in.readLine();
if (line == null) {
return null;
}
tokenizer = new StringTokenizer(line);
}
return tokenizer.nextToken();
}
private int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
}
Python 2 rep HackerRank Solution
# T = test cases (1-6)
# N = number of test integers (1-100000)
# Q = queries (1-50000)
# T
# N Q
# a_1 p_1 q_1 where
# q_1,p_1 are (1-N)
# a_1 is something (0 to 2^15)
# return maximum value
import sys
import math
class Node:
def __init__(self):
self.left = None
self.right = None
self.indices = None
self.val = None
#traverse_tree(tree)
def traverse_tree(tree):
if tree == None:
return
if tree.val != None:
print tree.val
print tree.indices
return
traverse_tree(tree.left)
traverse_tree(tree.right)
# bia: binary string of the desired number
# p,q : p <= i <= q must hold for the matched x_i.
# tree: whatever node we're looking at
# depth: depth of node in tree - 0 is root
def nearest_match(bia,p,q,tree,depth):
if depth == 14:
if bia[depth] == "1":
if (tree.right != None):
for i in tree.right.indices:
if (i >= p) and (i <= q):
return tree.right.val
if (tree.left != None):
for i in tree.left.indices:
if (i >= p) and (i <= q):
return tree.left.val
else:
if (tree.left != None):
for i in tree.left.indices:
if (i >= p) and (i <= q):
return tree.left.val
if (tree.right != None):
for i in tree.right.indices:
if (i >= p) and (i <= q):
return tree.right.val
return -1
if bia[depth] == "1":
if tree.right != None:
v = nearest_match(bia,p,q,tree.right,depth+1)
if v != -1:
return v
if tree.left != None:
v = nearest_match(bia,p,q,tree.left,depth+1)
return v
if bia[depth] == "0":
if tree.left != None:
v = nearest_match(bia,p,q,tree.left,depth+1)
if v != -1:
return v
if tree.right != None:
v = nearest_match(bia,p,q,tree.right,depth+1)
return v
return -1
def build_tree(N, xs):
root = Node()
cur_node = Node()
nodedict = {}
for i in range(N):
x_i = xs[i]
# Get bits
new_leaf = Node()
try:
nodedict[x_i].indices += [i+1]
continue
except KeyError:
pass
if ((x_i >> 14) & 1):
if (root.right == None):
root.right = Node()
cur_node = root.right
else:
if (root.left == None):
root.left = Node()
cur_node = root.left
for j in range(14):
if ((x_i >> (13-j)) & 1):
if (cur_node.right == None):
if j == 13:
cur_node.right = new_leaf
else:
cur_node.right = Node()
cur_node = cur_node.right
else:
if (cur_node.left == None):
if j == 13:
cur_node.left = new_leaf
else:
cur_node.left = Node()
cur_node = cur_node.left
# If at the leaf, add the index of x_i to the list.
if j == 13:
new_leaf.val = x_i
new_leaf.indices = [i+1]
nodedict[x_i] = new_leaf
return root
# MAIN
# Initialize the tree, begin the loop that searches.
# With the root at depth 0, leaves will be at depth 15, because
# the range of values of x_i go from [0,2^15)
MAX_SIZE = int(math.pow(2,15) - 1)
T = int(sys.stdin.readline())
for _ in range(T):
N, Q = map(int,sys.stdin.readline().split())
xs = map(int,sys.stdin.readline().rstrip("\n").split())
#build the tree. lchild is 0, rchild is 1
root = build_tree(N, xs)
#use dfs to check that it's all okay
# traverse_tree(root)
#Now, search for the inverse, or backtrack to find the next smallest value.
for y in range(Q):
a,p,q = map(int,sys.stdin.readline().split())
# Inverse of a
ia = a ^ MAX_SIZE
# Binary string of a. Get digits and then format to length 15
bia = bin(ia)[2:]
bia = "0" * (15 - len(bia)) + bia
# using this binary string, search for the nearest match in the tree.
# i.e., the value in the tree whose xor with a is the largest.
# this value is in fact the bitwise inverse of a.
print nearest_match(bia,p,q,root,0) ^ a
#to do: write the search algorithm that finds the closest match. this shouldnt be too hard witht he binary string lookup.
#make sure it works, and then fail miserably when it doesnt run fast enough -___-
Python 3 rep HackerRank Solution
C rep HackerRank Solution
#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 r <= q
} else if (r < p) {
left = mid + 1; // else p <= r <= q
} 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;
// first iteration
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("%d\n", a ^ table[j]);
}
}
free(table);
free(info);
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
