Table of Contents
Quadrant Queries – 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++ Quadrant Queries HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <memory.h>
const int maxn = 65536*2;
struct st_node{
int total[4];
bool x,y;
};
static st_node nodes[maxn*2-1];
int n;
int tree_insert(int node, int l, int r, int index, int* total){
for (int i=0; i<4; i++)
nodes[node].total[i] += total[i];
if (l<r){
int mid = (l+r)/2;
if (index<=mid)
tree_insert(node*2+1, l, mid, index, total);
else
tree_insert(node*2+2, mid+1, r, index, total);
}
}
int read_point(){
memset(nodes, 0, sizeof(nodes));
std::cin>>n;
for (int i=1; i<=n; i++){
int x,y;
int total[4];
memset(total, 0, sizeof(total));
std::cin>>x>>y;
if (x==0 && y==0)
continue;
if (x>0 && y>0)
total[0] = 1;
if (x<0 && y>0)
total[1] = 1;
if (x<0 && y<0)
total[2] = 1;
if (x>0 && y<0)
total[3] = 1;
tree_insert(0,1,n,i,total);
}
}
void swap(int &x, int&y){
x = x^y;
y = x^y;
x = x^y;
}
void reflect(int *total, bool xreflect, bool yreflect){
if (xreflect){
swap(total[0],total[3]);
swap(total[1],total[2]);
}
if (yreflect){
swap(total[0],total[1]);
swap(total[2],total[3]);
}
}
int tree_count(int node, int l, int r, int x, int y, int* total, bool xreflect, bool yreflect){
xreflect ^= nodes[node].x;
yreflect ^= nodes[node].y;
if (x<=l && r<=y){
int tmp[4];
for (int i=0; i<4; i++)
tmp[i] = nodes[node].total[i];
reflect(tmp, xreflect, yreflect);
for (int i=0; i<4; i++)
total[i] += tmp[i];
return 0;
}
if (l<r){
int mid = (l+r)/2;
if (x<=mid)
tree_count(node*2+1, l, mid, x, y, total, xreflect, yreflect);
if (y>=mid+1)
tree_count(node*2+2, mid+1, r, x, y, total, xreflect, yreflect);
}
}
int tree_reflect(int node, int l, int r, int x, int y, bool xreflect, bool yreflect){
if (x<=l && r<=y){
nodes[node].x ^= xreflect;
nodes[node].y ^= yreflect;
return 0;
}
if (l<r){
int mid=(l+r)/2;
if (x<=mid)
tree_reflect(node*2+1, l, mid, x, y, xreflect, yreflect);
if (y>=mid+1)
tree_reflect(node*2+2, mid+1, r, x, y, xreflect, yreflect);
int ltotal[4], rtotal[4];
for (int i=0; i<4; i++){
ltotal[i] = nodes[node*2+1].total[i];
rtotal[i] = nodes[node*2+2].total[i];
}
reflect(ltotal, nodes[node*2+1].x, nodes[node*2+1].y);
reflect(rtotal, nodes[node*2+2].x, nodes[node*2+2].y);
for (int i=0; i<4; i++)
nodes[node].total[i] = ltotal[i]+rtotal[i];
}
}
int solve(){
int q;
std::cin>>q;
for (int i=0; i<q; i++){
char type;
int x, y;
std::cin>>type>>x>>y;
if (type=='C'){
int total[4];
memset(total, 0, sizeof(total));
tree_count(0, 1, n, x, y, total, false, false);
std::cout<<total[0]<<" "<<total[1]<<" "<<total[2]<<" "<<total[3]<<std::endl;
}
else if (type=='X'){
tree_reflect(0, 1, n, x, y, true, false);
}
else if (type=='Y'){
tree_reflect(0, 1, n, x, y, false, true);
}
}
}
int main(){
read_point();
solve();
}
Java Quadrant Queries HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
private static final int[] BC = new int[1<<16];
public static void main(String[] argv) throws Exception {
prep();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line1 = br.readLine();
int N = Integer.parseInt(line1);
ArrayList<String> dump = new ArrayList<String>(100000);
int[] x = new int[N/32+1];
int[] y = new int[N/32+1];
long rs = System.currentTimeMillis();
for(int i=0;i<N;i++){
String line2 = br.readLine();
String[] tmp2 = line2.split(" ");
if(tmp2[0].charAt(0) != '-') x[i/32] |= 1<< i%32;
if(tmp2[1].charAt(0) != '-') y[i/32] |= 1<< i%32;
}
long re = System.currentTimeMillis();
String line3 = br.readLine();
int Q = Integer.parseInt(line3);
boolean wasC = false;
int[] tmp1 = new int[N/32+1];
int[] tmp24= new int[N/32+1];
int[] tmp2 = new int[N/32+1];
int[] cnt1 = new int[N/32+1];
int[] cnt24= new int[N/32+1];
int[] cnt2 = new int[N/32+1];
long ws = System.currentTimeMillis();
for(int i=0;i<Q;i++){
String line4 = br.readLine();
String[] tmp4 = line4.split(" ");
int sindex = Integer.parseInt(tmp4[1]);
int eindex = Integer.parseInt(tmp4[2]);
int sm = (sindex-1)%32;
int sn = (sindex-1)/32;
int em = eindex%32;
int en = eindex/32;
int es = eindex-sindex+1;
if(tmp4[0].equals("X")) {
if(sn == en){
int mask = ((1<<(es))-1)<<(sm);
y[en] ^= mask;
}else{
int mask = -1;
int fmask = mask<<(sm);
int emask = (1<<(em))-1;
y[sn] ^= fmask;
for(int j=sn+1;j<en;j++) y[j] ^= mask;
y[en] ^= emask;
}
wasC = false;
}else if(tmp4[0].equals("Y")) {
if(sn == en){
int mask = ((1<<(es))-1)<<(sm);
x[en] ^= mask;
}else{
int mask = -1;
int fmask = mask<<(sm);
int emask = (1<<(em))-1;
x[sn] ^= fmask;
for(int j=sn+1;j<en;j++) x[j] ^= mask;
x[en] ^= emask;
}
wasC = false;
}else{
/*
if(!wasC || wasC){
for(int j=0;j<x.length;j++) {
tmp1[j] = x[j] & y[j];
tmp24[j] = x[j] ^ y[j];
tmp2[j] = tmp24[j] & y[j];
cnt1[j] = bitCount(tmp1[j]);
cnt24[j]= bitCount(tmp24[j]);
cnt2[j] = bitCount(tmp2[j]);
}
}
*/
int maskes = ((1<<(es))-1)<<(sm);
int maskall = -1;
int fmask = maskall<<(sm);
int emask = (1<<(em))-1;
// 1st quadrant x bit: 1, y bit: 1 (x & y)
int c1 = 0;
if(sn == en){
c1 += bitCount(x[en] & y[en] & maskes);
}else{
c1 += bitCount(x[sn] & y[sn] & fmask);
for(int j=sn+1;j<en;j++) c1 += bitCount(x[j] & y[j]);
c1 += bitCount(x[en] & y[en] & emask);
}
// 2nd quadrant x bit: 0, y bit: 1
// 4th quadrant x bit: 1, y bit: 0
// x xor y = c2 + c4
// (x xor y) & y = c2
int c24 = 0;
int c2 = 0;
if(sn == en){
int t2 = (x[en] ^ y[en]) & maskes;
c24 += bitCount(t2);
c2 += bitCount(t2 & y[en]);
}else{
int t2 = (x[sn] ^ y[sn]) & fmask;
c24 += bitCount(t2);
c2 += bitCount(t2 & y[sn]);
for(int j=sn+1;j<en;j++) {
t2 = x[j] ^ y[j];
c24 += bitCount(t2);
c2 += bitCount(t2 & y[j]);
}
t2 = (x[en] ^ y[en]) & emask;
c24 += bitCount(t2);
c2 += bitCount(t2 & y[en]);
}
int c4 = c24 - c2;
// 3rd quadrant x bit: 0, y bit: 0 (total - c1 - c2 - c4)
int c3 = eindex - sindex + 1 - c1 - c2 - c4;
dump.add(c1+" "+c2+" "+c3+" "+c4);
//System.out.println(c1+" "+c2+" "+c3+" "+c4);
wasC = true;
}
}
long we = System.currentTimeMillis();
for(int i=0;i<dump.size();i++) System.out.println(dump.get(i));
br.close();
//System.out.println("R:"+(re-rs));
//System.out.println("W:"+(we-ws));
}
private static void prep() {
int max = 1<<16;
int step1 = 1<<8;
for(int i=0;i<step1;i++) BC[i] = Integer.bitCount(i);
for(int i=step1;i<max;i++){
BC[i] = BC[i&0xFF] + BC[(i>>8)&0xFF];
}
}
private static int bitCount(int i){
return BC[i&0xFFFF] + BC[(i>>16)&0xFFFF];
}
}
Python 2 Quadrant Queries HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <memory.h>
const int maxn = 65536*2;
struct st_node{
int total[4];
bool x,y;
};
static st_node nodes[maxn*2-1];
int n;
int tree_insert(int node, int l, int r, int index, int* total){
for (int i=0; i<4; i++)
nodes[node].total[i] += total[i];
if (l<r){
int mid = (l+r)/2;
if (index<=mid)
tree_insert(node*2+1, l, mid, index, total);
else
tree_insert(node*2+2, mid+1, r, index, total);
}
}
int read_point(){
memset(nodes, 0, sizeof(nodes));
std::cin>>n;
for (int i=1; i<=n; i++){
int x,y;
int total[4];
memset(total, 0, sizeof(total));
std::cin>>x>>y;
if (x==0 && y==0)
continue;
if (x>0 && y>0)
total[0] = 1;
if (x<0 && y>0)
total[1] = 1;
if (x<0 && y<0)
total[2] = 1;
if (x>0 && y<0)
total[3] = 1;
tree_insert(0,1,n,i,total);
}
}
void swap(int &x, int&y){
x = x^y;
y = x^y;
x = x^y;
}
void reflect(int *total, bool xreflect, bool yreflect){
if (xreflect){
swap(total[0],total[3]);
swap(total[1],total[2]);
}
if (yreflect){
swap(total[0],total[1]);
swap(total[2],total[3]);
}
}
int tree_count(int node, int l, int r, int x, int y, int* total, bool xreflect, bool yreflect){
xreflect ^= nodes[node].x;
yreflect ^= nodes[node].y;
if (x<=l && r<=y){
int tmp[4];
for (int i=0; i<4; i++)
tmp[i] = nodes[node].total[i];
reflect(tmp, xreflect, yreflect);
for (int i=0; i<4; i++)
total[i] += tmp[i];
return 0;
}
if (l<r){
int mid = (l+r)/2;
if (x<=mid)
tree_count(node*2+1, l, mid, x, y, total, xreflect, yreflect);
if (y>=mid+1)
tree_count(node*2+2, mid+1, r, x, y, total, xreflect, yreflect);
}
}
int tree_reflect(int node, int l, int r, int x, int y, bool xreflect, bool yreflect){
if (x<=l && r<=y){
nodes[node].x ^= xreflect;
nodes[node].y ^= yreflect;
return 0;
}
if (l<r){
int mid=(l+r)/2;
if (x<=mid)
tree_reflect(node*2+1, l, mid, x, y, xreflect, yreflect);
if (y>=mid+1)
tree_reflect(node*2+2, mid+1, r, x, y, xreflect, yreflect);
int ltotal[4], rtotal[4];
for (int i=0; i<4; i++){
ltotal[i] = nodes[node*2+1].total[i];
rtotal[i] = nodes[node*2+2].total[i];
}
reflect(ltotal, nodes[node*2+1].x, nodes[node*2+1].y);
reflect(rtotal, nodes[node*2+2].x, nodes[node*2+2].y);
for (int i=0; i<4; i++)
nodes[node].total[i] = ltotal[i]+rtotal[i];
}
}
int solve(){
int q;
std::cin>>q;
for (int i=0; i<q; i++){
char type;
int x, y;
std::cin>>type>>x>>y;
if (type=='C'){
int total[4];
memset(total, 0, sizeof(total));
tree_count(0, 1, n, x, y, total, false, false);
std::cout<<total[0]<<" "<<total[1]<<" "<<total[2]<<" "<<total[3]<<std::endl;
}
else if (type=='X'){
tree_reflect(0, 1, n, x, y, true, false);
}
else if (type=='Y'){
tree_reflect(0, 1, n, x, y, false, true);
}
}
}
int main(){
read_point();
solve();
}
C Quadrant Queries HackerRank Solution
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
enum {
XAXIS = 0,
YAXIS = 1
};
/*
* Binary tree.
* Nodes at level k summarize a subtree of size 2^k.
* The level and range is implicit.
*/
typedef struct node node;
struct node {
int count;
node *left, *right;
};
node *pool;
int nnodes, npool;
typedef struct tree tree;
struct tree {
node *root[4];
int nlevels;
};
node *newnode() {
assert(nnodes < npool);
return &pool[nnodes++];
}
node *mktree(int level) {
node *np;
np = newnode();
if (level == 0)
return np;
np->left = mktree(level-1);
np->right = mktree(level-1);
return np;
}
tree *inittree(int n) {
tree *tp;
int i;
tp = (tree *) malloc(sizeof(*tp));
if (tp == NULL)
exit(1);
tp->nlevels = 0;
while ((1 << tp->nlevels) < n)
tp->nlevels++;
npool = 4 * (1 << (tp->nlevels+1));
pool = calloc(npool, sizeof(node));
if (pool == NULL)
exit(1);
for (i = 0; i < 4; i++)
tp->root[i] = mktree(tp->nlevels);
return tp;
}
void _add(node *np, int lvl, int idx, int x) {
int lt, rt, mid;
np->count++;
if (lvl == 0)
return;
lt = (1<<lvl) * idx;
mid = lt + (1<<(lvl-1));
rt = lt + (1<<lvl) - 1;
assert(lt <= x && x <= rt);
if (x < mid)
_add(np->left, lvl-1, 2*idx, x);
else
_add(np->right, lvl-1, 2*idx + 1, x);
}
/* Add a value at x in quadrant q. */
void add(tree *tp, int x, int q) {
_add(tp->root[q], tp->nlevels, 0, x);
}
int _count(node *np, int lvl, int idx, int l, int r) {
int lt, rt;
lt = (1<<lvl) * idx;
rt = lt + (1<<lvl) - 1;
/* Out of bounds. */
if (r < lt) return 0;
if (l > rt) return 0;
/* Whole range. */
if (l <= lt && rt <= r)
return np->count;
/* Left and right children. */
return _count(np->left, lvl-1, 2*idx, l, r) +
_count(np->right, lvl-1, 2*idx + 1, l, r);
}
/* count: print # in each quadrant from l -> r inclusive. */
void count(tree *tp, int l, int r) {
int q[4];
int i;
for (i = 0; i < 4; i++)
q[i] = _count(tp->root[i], tp->nlevels, 0, l, r);
printf("%d %d %d %d\n", q[0], q[1], q[2], q[3]);
}
void _flip(node **np, int lvl, int idx, int l, int r, int typ) {
int lt, rt, i;
node *tmp, *lp[4], *rp[4];
lt = (1<<lvl) * idx;
rt = lt + (1<<lvl) - 1;
/* Out of bounds. */
if (r < lt) return;
if (l > rt) return;
/* Whole range. */
if (l <= lt && rt <= r) {
assert(typ == XAXIS || typ == YAXIS);
switch (typ) {
case XAXIS:
tmp = np[0]; np[0] = np[3]; np[3] = tmp;
tmp = np[1]; np[1] = np[2]; np[2] = tmp;
break;
case YAXIS:
tmp = np[0]; np[0] = np[1]; np[1] = tmp;
tmp = np[2]; np[2] = np[3]; np[3] = tmp;
break;
default:
assert(0);
break;
}
return;
}
assert(lvl > 0);
/* Left and right children. */
for (i = 0; i < 4; i++) {
lp[i] = np[i]->left;
rp[i] = np[i]->right;
}
_flip(lp, lvl-1, 2*idx, l, r, typ);
_flip(rp, lvl-1, 2*idx + 1, l, r, typ);
for (i = 0; i < 4; i++) {
np[i]->left = lp[i];
np[i]->right = rp[i];
np[i]->count = lp[i]->count + rp[i]->count;
}
}
/* flip: flip points about axis. */
void flip(tree *tp, int l, int r, int typ) {
_flip(tp->root, tp->nlevels, 0, l, r, typ);
}
int quadrant(int x, int y) {
if (x > 0 && y > 0) return 0;
if (x < 0 && y > 0) return 1;
if (x < 0 && y < 0) return 2;
if (x > 0 && y < 0) return 3;
/* shouldn't get here */
assert(0);
return -1;
}
int main() {
int i, x, y, a, b, npoints, nqueries;
char query;
tree *tp;
if (scanf(" %d", &npoints) != 1)
return 1;
tp = inittree(npoints);
for (i = 0; i < npoints; i++) {
if (scanf(" %d %d", &x, &y) != 2)
return 1;
if (x == 0 || y == 0)
return 1;
add(tp, i, quadrant(x, y));
}
if (scanf(" %d", &nqueries) != 1)
return 1;
for (i = 0; i < nqueries; i++) {
if (scanf(" %c %d %d", &query, &a, &b) != 3)
return 1;
switch (query) {
case 'C':
count(tp, a-1, b-1);
break;
case 'X':
flip(tp, a-1, b-1, XAXIS);
break;
case 'Y':
flip(tp, a-1, b-1, YAXIS);
break;
default:
return 1;
}
}
return 0;
}
Leave a comment below
