Table of Contents
Kth Ancestor – 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++ Kth Ancestor HackerRank Solution
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define REP(i, N) FOR(i, 0, N)
#define RREP(i, N) RFOR(i, N, 0)
#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
typedef long long Int;
typedef unsigned long long UInt;
typedef vector <int> VI;
typedef pair <int, int> PII;
VI a[1<<17];
int n, root;
int dist[1<<17];
int p[1<<17][17];
int st[1<<17];
int deep;
void dfs(int cur)
{
dist[cur] = deep;
st[deep++] = cur;
for (int i = 1, lev = 0; i < deep; i<<=1, ++lev)
{
p[cur][lev] = st[deep - i];
}
REP(i,SZ(a[cur]))
{
int nx = a[cur][i];
if (nx == p[cur][0])
continue;
dfs(nx);
}
--deep;
}
int get(int cur,int len)
{
if (cur <= 0 || cur > 100000 || dist[cur] <= 0)
return -1;
int need = dist[cur] - len;
if (need < 0)
return -1;
if (need == 0)
return root;
int go = 0;
int step = 0;
while (dist[cur] != need)
{
if (++step > 10000)
throw -1;
int* pp = p[cur];
int nx = pp[go];
while (go < 16 && dist[nx] > need)
{
++go;
nx = pp[go];
}
while (nx <= 0 || dist[nx] < need)
{
--go;
nx = pp[go];
}
cur = pp[go];
}
return cur;
}
void add(int par, int cur)
{
if (par == 0)
{
dist[cur] = 0;
memset(p[cur], 0, sizeof(p[cur]));
return;
}
dist[cur] = dist[par] + 1;
REP(i,17)
{
p[cur][i] = get(par, (1<<i)-1);
}
}
void del(int cur)
{
dist[cur] = -1;
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int T;
cin>>T;
REP(tests,T)
{
memset(dist, -1, sizeof(dist));
if (tests > 0)
memset(p,0,sizeof(p));
REP(i,(1<<17))
a[i].clear();
scanf("%d", &n);
REP(i,n)
{
int x,y;
scanf("%d%d", &x,&y);
if (y == 0)
{
root = x;
continue;
}
a[y].push_back(x);
}
dfs(root);
int q;
scanf("%d",&q);
REP(i,q)
{
int c, x,y;
scanf("%d", &c);
switch (c)
{
case 0:
scanf("%d%d",&x,&y);
add(x, y);
break;
case 1:
scanf("%d",&x);
del(x);
break;
case 2:
scanf("%d%d",&x,&y);
int res = get(x,y);
if (res == -1)
res = 0;
printf("%d\n", res);
break;
}
}
}
return 0;
}
Java Kth Ancestor HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution{
private BufferedReader in;
private StringTokenizer st;
private PrintWriter out;
int[][]parent ;
void process(){
for (int j = 1; j < 17; j++) {
for (int i = 1; i < parent.length; i++) {
parent[i][j] = parent[parent[i][j-1]][j-1];
}
}
}
void ancestor(int x, int k){
int node = x;
for(int j = 16;j>=0;j--){
if( (k&(1<<j)) != 0){
node = parent[node][j];
if(node == 0) break;
}
}
out.println(node);
}
void solve() throws IOException{
int t = nextInt();
while(t-->0){
parent = new int[100000+1][17];
int p = nextInt();
while(p-->0){
parent[nextInt()][0] = nextInt();
}
int q = nextInt();
process();
while(q-->0){
int type = nextInt();
if(type == 0){
int nodep = nextInt();
int node = nextInt();
parent[node][0] = nodep;
for (int j = 1; j < 17; j++) {
parent[node][j] = parent[parent[node][j-1]][j-1];
}
}
else if(type == 1){
int node = nextInt();
for (int j = 0; j < 17; j++) {
parent[node][j] = 0;
}
}
else if(type == 2){
int node = nextInt();
int k = nextInt();
ancestor(node,k);
}
}
}
}
Solution() throws IOException {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
eat("");
solve();
out.close();
}
private void eat(String str) {
st = new StringTokenizer(str);
}
String next() throws IOException {
while (!st.hasMoreTokens()) {
String line = in.readLine();
if (line == null) {
return null;
}
eat(line);
}
return st.nextToken();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
long nextLong() throws IOException {
return Long.parseLong(next());
}
double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public static void main(String[] args) throws IOException {
new Solution();
}
int gcd(int a,int b){
if(b>a) return gcd(b,a);
if(b==0) return a;
return gcd(b,a%b);
}
}
Python 3 Kth Ancestor HackerRank Solution
def go():
I=lambda:map(int,input().split())
N=100002
d=[0]*N
P=[0]*N
def add(p,c):
d[c]=d[p]+1
v=[p]
for i in range(17):
if not P[p] or len(P[p])<=i:break
p=P[p][i];v.append(p)
P[c]=v
c=[[]for i in range(N)]
for i in range(next(I())):
x,y=I()
if y: c[y].append(x)
else: R=x
l=[R]
while l:
p=l.pop()
l.extend(c[p])
for h in c[p]:
add(p,h)
del c,l
for i in range(next(I())):
l=list(I())
if l[0]>1:
_,x,k=l
if d[x]<k:print(0);continue
for i in range(17):
if (1<<i)&k:x=P[x][i]
print(x)
elif l[0]:d[l[1]]=0
else:add(l[1],l[2])
for t in range(int(input())):
go()
Python 2 Kth Ancestor HackerRank Solution
#!/usr/bin/python
from math import log
def doit():
p = input()
pairs = []
for x in xrange(p):
a, b = map(int, raw_input().strip().split())
pairs.append((a,b))
q = input()
limit = max(int(log(p + q) / log(2) + 2), 17) # levels
ances = {a: [0] * limit for a, _ in pairs}
# init
for a, b in pairs:
ances[a][0] = b
# build
for x in xrange(1, limit):
for v in ances:
p = ances[v][x-1]
if p == 0:
continue
ances[v][x] = ances[p][x-1]
#print ances
def get(a, k):
#print 'get', a, k
if a not in ances:
return 0
if k == 0:
return a
i = 0
while k >= (1<<(i+1)):
i += 1
k -= 1 << i
return get(ances[a][i], k)
# queries
for i in xrange(q):
nums = map(int, raw_input().strip().split())
if nums[0] == 0: # add
x, y = nums[1:]
if y not in ances:
ances[y] = [0]*limit
ances[y][0] = x
for k in xrange(1, limit):
p = ances[y][k-1]
if p == 0:
break
ances[y][k] = ances[p][k-1]
#print ances
elif nums[0] == 1: # remove
x = nums[1]
del ances[x]
else: # query
x, k = nums[1:]
if x not in ances:
print 0
else:
while k > 0 and x > 0:
i = 0
while (k & (1<<i)) == 0:
i += 1
if i >= len(ances[x]):
x = 0
break
x = ances[x][i]
k -= 1 << i
print x
t = input()
for x in xrange(t):
doit()
C Kth Ancestor HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int LENGTHLIMIT = 17;
int main(void);
void solveone(void);
void insert(int* nodes, int X, int Y);
int find(int* nodes, int X, int Y);
int main(void) {
int T = 0;
scanf("%d\n", &T);
for(int t = 0; t < T; t++) {
solveone();
}
}
void solveone(void) {
int* nodes = malloc(100001*LENGTHLIMIT*sizeof(int));
memset(nodes, 0, 100001*LENGTHLIMIT*sizeof(int));
int P, Q, kind, X, Y;
scanf("%d\n", &P);
for(int p = 0; p < P; p++){
scanf("%d %d\n", &X, &Y);
insert(nodes, X, Y);
}
scanf("%d\n", &Q);
for(int q = 0; q < Q; q++) {
scanf("%d ", &kind);
switch(kind) {
case 0:
scanf("%d %d\n", &X, &Y);
insert(nodes, Y, X);
break;
case 1:
scanf("%d\n", &X);
memset(nodes+LENGTHLIMIT*X, 0, LENGTHLIMIT*sizeof(int));
break;
default: // 2
scanf("%d %d\n", &X, &Y);
printf("%d\n", find(nodes, X, Y));
}
}
free(nodes);
}
void insert(int* nodes, int X, int Y) {
int* nodesX = nodes + X*LENGTHLIMIT;
nodesX[0] = Y;
nodesX[1] = nodes[nodesX[0]*LENGTHLIMIT+0];
nodesX[2] = nodes[nodesX[1]*LENGTHLIMIT+1];
nodesX[3] = nodes[nodesX[2]*LENGTHLIMIT+2];
nodesX[4] = nodes[nodesX[3]*LENGTHLIMIT+3];
nodesX[5] = nodes[nodesX[4]*LENGTHLIMIT+4];
nodesX[6] = nodes[nodesX[5]*LENGTHLIMIT+5];
nodesX[7] = nodes[nodesX[6]*LENGTHLIMIT+6];
nodesX[8] = nodes[nodesX[7]*LENGTHLIMIT+7];
nodesX[9] = nodes[nodesX[8]*LENGTHLIMIT+8];
nodesX[10] = nodes[nodesX[9]*LENGTHLIMIT+9];
nodesX[11] = nodes[nodesX[10]*LENGTHLIMIT+10];
nodesX[12] = nodes[nodesX[11]*LENGTHLIMIT+11];
nodesX[13] = nodes[nodesX[12]*LENGTHLIMIT+12];
nodesX[14] = nodes[nodesX[13]*LENGTHLIMIT+13];
nodesX[15] = nodes[nodesX[14]*LENGTHLIMIT+14];
nodesX[16] = nodes[nodesX[15]*LENGTHLIMIT+15];
}
int find(int* nodes, int X, int Y) {
if((nodes+X*LENGTHLIMIT)[0] == 0) {
return 0;
}
int tmp = X;
unsigned int idx = 0;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
idx++;
if( (Y&(1<<idx)) != 0 ) {
tmp = (nodes+tmp*LENGTHLIMIT)[idx];
}
return tmp;
}
Leave a comment below
