Table of Contents
Move the Coins – 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 <cstdio>
#include <iostream>
#include <ctime>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstring>
using namespace std;
#define N 1000000
int Time, n, x, y, q, c[N];
int L[N], R[N], ni[N][2], dep[N];
vector <int> ve[N];
void dfs(int k, int f) {
L[k] = ++Time;
ni[k][dep[k]] = c[k];
for (int i = 0; i < (int) ve[k].size(); i++)
if (ve[k][i] != f) {
dep[ve[k][i]] = dep[k] ^ 1;
dfs(ve[k][i], k);
ni[k][0] ^= ni[ve[k][i]][0];
ni[k][1] ^= ni[ve[k][i]][1];
}
R[k] = Time;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (int i = 1; i < n; i++) {
scanf("%d%d", &x, &y);
ve[x].push_back(y);
ve[y].push_back(x);
}
dep[1] = 0;
dfs(1, 0);
scanf("%d", &q);
while (q--) {
scanf("%d%d", &x, &y);
if (L[x] <= L[y] && L[y] <= R[x])
printf("INVALID\n");
else {
if ((dep[y] + dep[x]) % 2 == 1) {
if (ni[1][1])
printf("YES\n");
else
printf("NO\n");
}else {
if (ni[1][1] ^ ni[x][1] ^ ni[x][0])
printf("YES\n");
else
printf("NO\n");
}
}
}
}
Java rep HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class E {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni();
int[] a = na(n);
int[] from = new int[n - 1];
int[] to = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
from[i] = ni() - 1;
to[i] = ni() - 1;
}
int[][] g = packU(n, from, to);
int[][] pars = parents3(g, 0);
int[] par = pars[0], ord = pars[1], dep = pars[2];
int[][] spar = logstepParents(par);
int[][] des = new int[2][n];
for(int i = n-1;i >= 0;i--){
int cur = ord[i];
des[0][cur] ^= a[cur];
for(int e : g[cur]){
if(par[cur] != e){
des[0][cur] ^= des[1][e];
des[1][cur] ^= des[0][e];
}
}
}
for(int Q = ni();Q > 0;Q--){
int x = ni()-1, y = ni()-1;
if(dep[x] < dep[y] && ancestor(y, dep[y]-dep[x], spar) == x){
out.println("INVALID");
continue;
}
int nim = des[1][0];
if(dep[x] % 2 == 0){
nim ^= des[1][x];
}else{
nim ^= des[0][x];
}
if(dep[y] % 2 == 1){
nim ^= des[1][x];
}else{
nim ^= des[0][x];
}
if(nim != 0){
out.println("YES");
}else{
out.println("NO");
}
}
}
public static int lca2(int a, int b, int[][] spar, int[] depth) {
if (depth[a] < depth[b]) {
b = ancestor(b, depth[b] - depth[a], spar);
} else if (depth[a] > depth[b]) {
a = ancestor(a, depth[a] - depth[b], spar);
}
if (a == b)
return a;
int sa = a, sb = b;
for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
.numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
if ((low ^ high) >= t) {
if (spar[k][sa] != spar[k][sb]) {
low |= t;
sa = spar[k][sa];
sb = spar[k][sb];
} else {
high = low | t - 1;
}
}
}
return spar[0][sa];
}
protected static int ancestor(int a, int m, int[][] spar) {
for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
if ((m & 1) == 1)
a = spar[i][a];
}
return a;
}
public static int[][] logstepParents(int[] par) {
int n = par.length;
int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
int[][] pars = new int[m][n];
pars[0] = par;
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
pars[j][i] = pars[j - 1][i] == -1 ? -1
: pars[j - 1][pars[j - 1][i]];
}
}
return pars;
}
public static int[][] parents3(int[][] g, int root) {
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] depth = new int[n];
depth[0] = 0;
int[] q = new int[n];
q[0] = root;
for (int p = 0, r = 1; p < r; p++) {
int cur = q[p];
for (int nex : g[cur]) {
if (par[cur] != nex) {
q[r++] = nex;
par[nex] = cur;
depth[nex] = depth[cur] + 1;
}
}
}
return new int[][] { par, q, depth };
}
static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for (int f : from)
p[f]++;
for (int t : to)
p[t]++;
for (int i = 0; i < n; i++)
g[i] = new int[p[i]];
for (int i = 0; i < from.length; i++) {
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new E().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 rep HackerRank Solution
n = input()
c = map(int, raw_input().strip().split())
adj = [[] for i in xrange(n)]
for ee in xrange(n-1):
a, b = map(int, raw_input().strip().split())
a -= 1
b -= 1
adj[a].append(b)
adj[b].append(a)
parent = [-1]*n
height = [0]*n
queue = [0]
parent[0] = 0
anc = [[0]*18 for i in xrange(n)]
xor = [[0,0] for i in xrange(n)]
f = 0
while f < len(queue):
i = queue[f]; f += 1
for j in adj[i]:
if j == parent[i]: continue
if parent[j] == -1:
parent[j] = i
height[j] = height[i] + 1
queue.append(j)
curr = anc[i][0] = parent[i]
for j in xrange(1,18):
curr = anc[i][j] = anc[curr][j-1]
xor[i][0] = c[i]
for i in reversed(queue):
p = parent[i]
if i != p:
xor[p][0] ^= xor[i][1]
xor[p][1] ^= xor[i][0]
def anc_si_ni(a,b):
d = height[b] - height[a]
if d < 0: return False
k = 0
while d:
if d & 1:
b = anc[b][k]
d >>= 1
k += 1
return a == b
for qq in xrange(input()):
a, b = map(int, raw_input().strip().split())
a -= 1
b -= 1
print 'INVALID' if anc_si_ni(a,b) else 'YES' if xor[0][1] ^ xor[a][1] ^ xor[a][(height[a] ^ height[b]) & 1] else 'NO'
Python 2 rep HackerRank Solution
from collections import deque
n = int(input())
G = [[int(c), 0, []] for c in input().strip().split()]
G[0][2].append(0)
parity = [True for i in range(n)]
order = [[-1,-1] for i in range(n)]
for i in range(n-1):
v1, v2 = (int(v)-1 for v in input().strip().split())
G[v1][2].append(v2)
G[v2][2].append(v1)
total = 0
pre = 0
post = 0
parent = deque([0])
while (len(parent) > 0):
node = parent.pop()
if (order[node][0] == -1):
order[node][0] = pre
pre += 1
parity[node] = not parity[G[node][1]]
if (parity[node]):
total = total ^ G[node][0]
G[node][2].remove(G[node][1])
if (len(G[node][2]) == 0):
parent.append(node)
else:
for c in G[node][2]:
G[c][1] = node
parent.append(c)
else:
order[node][1] = post
post += 1
for c in G[node][2]:
G[node][0] = G[node][0] ^ G[c][0]
if (G[G[node][1]][2][0] == node):
parent.append(G[node][1])
q = int(input())
for i in range(q):
u, v = (int(vertex)-1 for vertex in input().strip().split())
if (order[u][0] < order[v][0] and order[u][1] > order[v][1]):
print("INVALID")
elif (parity[u] == parity[v]):
newtotal = G[u][0]
if (newtotal ^ total == 0):
print("NO")
else:
print("YES")
else:
if (total == 0):
print("NO")
else:
print("YES")
C rep HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
typedef struct _lnode {
int x;
int w;
struct _lnode *next;
} lnode;
void insert_edge(int x, int y, int w);
void preprocess();
int lca(int a, int b);
void dfs0(int u);
int a[50000], level[50000], odd[50000] = {0}, even[50000] = {0}, DP[16][50000],
n;
lnode *table[50000] = {0};
int main() {
int q, x, y, t, i;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", a + i);
for (i = 0; i < n - 1; i++) {
scanf("%d%d", &x, &y);
insert_edge(x - 1, y - 1, 1);
}
preprocess();
scanf("%d", &q);
while (q--) {
scanf("%d%d", &x, &y);
x--;
y--;
if (lca(x, y) == x)
printf("INVALID\n");
else {
t = odd[0];
if (level[x] % 2)
t ^= even[x];
else
t ^= odd[x];
if (level[y] % 2)
t ^= odd[x];
else
t ^= even[x];
if (t)
printf("YES\n");
else
printf("NO\n");
}
}
return 0;
}
void insert_edge(int x, int y, int w) {
lnode *t = malloc(sizeof(lnode));
t->x = y;
t->w = w;
t->next = table[x];
table[x] = t;
t = malloc(sizeof(lnode));
t->x = x;
t->w = w;
t->next = table[y];
table[y] = t;
return;
}
void preprocess() {
int i, j;
level[0] = 0;
DP[0][0] = 0;
dfs0(0);
for (i = 1; i < 16; i++)
for (j = 0; j < n; j++)
DP[i][j] = DP[i - 1][DP[i - 1][j]];
return;
}
int lca(int a, int b) {
int i;
if (level[a] > level[b]) {
i = a;
a = b;
b = i;
}
int d = level[b] - level[a];
for (i = 0; i < 16; i++)
if (d & (1 << i))
b = DP[i][b];
if (a == b)
return a;
for (i = 15; i >= 0; i--)
if (DP[i][a] != DP[i][b])
a = DP[i][a], b = DP[i][b];
return DP[0][a];
}
void dfs0(int u) {
lnode *x;
even[u] ^= a[u];
for (x = table[u]; x; x = x->next)
if (x->x != DP[0][u]) {
DP[0][x->x] = u;
level[x->x] = level[u] + 1;
dfs0(x->x);
even[u] ^= odd[x->x];
odd[u] ^= even[x->x];
}
return;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
