Similar Pair – 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++ Similar Pair HackerRank Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, aib[200005];
inline int lsb(int & x){
return x & -x;
}
void update(int val, int pos){
for(int i = pos; i <= n * 2; i += lsb(i))
aib[i] += val;
}
int query(int pos){
int rval = 0;
for(int i = pos; i > 0; i -= lsb(i))
rval += aib[i];
return rval;
}
vector<int> graph[100005];
int t, dad[100005];
long long ans;
void dfs(int x){
ans += (long long)query(x + t) - query(x - t - 1);
update(1, x);
for(int i = 0; i < graph[x].size(); ++i)
dfs(graph[x][i]);
update(-1, x);
}
int main() {
cin >> n >> t;
for(int i = 1; i < n; ++i){
int x, y;
cin >> x >> y;
dad[y] = x;
graph[x].push_back(y);
}
for(int i = 1; i <= n; ++i)
if(!dad[i])
dfs(i);
cout << ans;
return 0;
}
Java Similar Pair HackerRank Solution
import java.awt.Point;
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import static java.lang.Math.*;
public class Solution implements Runnable {
BufferedReader in;
PrintWriter out;
StringTokenizer tok = new StringTokenizer("");
public static void main(String[] args) {
new Thread(null, new Solution(), "", 256 * (1L << 20)).start();
}
public void run() {
try {
long t1 = System.currentTimeMillis();
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
// in = new BufferedReader(new FileReader("src/input.txt"));
Locale.setDefault(Locale.US);
solve();
in.close();
out.close();
long t2 = System.currentTimeMillis();
System.err.println("Time = " + (t2 - t1));
} catch (Throwable t) {
t.printStackTrace(System.err);
System.exit(-1);
}
}
String readString() throws IOException {
while (!tok.hasMoreTokens()) {
tok = new StringTokenizer(in.readLine());
}
return tok.nextToken();
}
int readInt() throws IOException {
return Integer.parseInt(readString());
}
long readLong() throws IOException {
return Long.parseLong(readString());
}
double readDouble() throws IOException {
return Double.parseDouble(readString());
}
Edge[] first;
FenwickTree sum;
long result;
void solve() throws IOException {
int n = readInt();
int k = readInt();
first = new Edge[n];
boolean[] root = new boolean[n];
Arrays.fill(root, true);
for (int i = 0; i < n - 1; i++) {
int from = readInt() - 1;
int to = readInt() - 1;
root[to] = false;
first[from] = new Edge(from, to, first[from]);
}
sum = new FenwickTree(n);
result = 0;
for (int i = 0; i < n; i++) {
if (root[i]) {
dfs(i, k);
break;
}
}
out.println(result);
}
void dfs(int x, int k)
{
result += sum.find(x + k) - sum.find(x - k - 1);
sum.increase(x, +1);
for (Edge edge = first[x]; edge != null; edge = edge.next)
{
dfs(edge.b, k);
}
sum.increase(x, -1);
}
class Edge {
int a;
int b;
Edge next;
Edge(int a, int b, Edge next) {
this.a = a;
this.b = b;
this.next = next;
}
}
class FenwickTree {
private int[] sum;
FenwickTree(int size) {
sum = new int[size + 10];
}
private int prev(int x) {
return x & (x - 1);
}
private int next(int x) {
return 2 * x - prev(x);
}
void increase(int id, int value) {
id++;
while (id < sum.length) {
sum[id] += value;
id = next(id);
}
}
long find(int id) {
id++;
id = Math.min(sum.length - 1, id);
long res = 0;
if (id <= 0) {
return 0;
}
while (id > 0) {
res += sum[id];
id = prev(id);
}
return res;
}
}
}
Python 3 Similar Pair HackerRank Solution
import resource
import sys
sys.setrecursionlimit(2000000)
#resource.setrlimit(resource.RLIMIT_STACK, (resource.RLIM_INFINITY, resource.RLIM_INFINITY))
def add(x, v):
x += 1
while x <= n:
a[x] += v
x += x & -x
def que(x):
x += 1
if x <= 0:
return 0
ret = 0
x = min(n, x)
while x > 0:
ret += a[x]
x -= x & -x
return ret
st = []
vis = {}
def dfs(x):
global ans
st.append(x)
while st:
x = st[-1]
if not x in vis:
ans += que(x + T) - que(x - T - 1)
add(x, 1)
vis[x] = 1
if nx[x]:
st.append(nx[x][-1])
nx[x].pop()
else:
st.pop()
add(x, -1)
n, T = (int(x) for x in input().split())
a = [0 for i in range(4 * n)]
nx = [[] for i in range(n)]
pre = [-1 for i in range(n)]
for i in range(n - 1):
s, e = (int(x) - 1 for x in input().split())
nx[s].append(e)
pre[e] = s
s = 1
while pre[s] != -1:
s = pre[s]
ans = 0
dfs(s)
print(ans)
Python 2 Similar Pair HackerRank Solution
#!/usr/bin/python
import sys
sys.setrecursionlimit(10000)
class Bit:
def __init__(self, n):
self.array = [0] * (n+1)
self.size = n
def add(self, idx, val = 1):
while idx <= self.size:
self.array[idx] += val
idx += idx & -idx
def get(self, idx):
ret = 0
while idx > 0:
ret += self.array[idx]
idx -= idx & -idx
return ret
'''
def dfs(now, parent, bit):
ret = bit.get(min(now+t, n)) - bit.get(now-t-1)
#print now, ret
bit.add(now)
for x in tree[now]:
if x != parent:
ret += dfs(x, now, bit)
bit.add(now, -1)
return ret
'''
def dfs(now, parent, bit):
ret = 0
stack = [now]
bit.add(now)
next = [0] * (n+1)
while len(stack) > 0:
now = stack[-1]
idx = next[now]
if idx < len(tree[now]):
child = tree[now][idx]
#print 'stack push', child
ret += bit.get(min(child+t, n)) - bit.get(child-t-1)
stack.append(child)
bit.add(child)
next[now] += 1
else:
#print 'stack pop', now
stack.pop()
bit.add(now, -1)
return ret
n, t = map(int, raw_input().strip().split())
tree = [[] for x in xrange(n+1)]
isroot = [True] * (n+1)
for x in xrange(n-1):
a, b = map(int, raw_input().strip().split())
tree[a].append(b)
isroot[b] = False
for x in xrange(1, n+1):
if isroot[x]: # root
print dfs(x, -1, Bit(n))
break
C Similar Pair HackerRank Solution
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "math.h"
typedef struct Node
{
struct Node *parent;
struct Node *peer_next;
struct Node *child_list;
int val;
struct Node *hash_next;
}Node;
unsigned long long int count;
unsigned int n,T,size;
Node **hash;
Node *root=NULL;
unsigned int diff(int a, int b)
{
if(a>b) return (a-b);
else return (b-a);
}
void countup(Node *x)
{
int i,val;
if(!x || !x->parent) return;
if((n-T) < size)
{
count+=size;
for(i=0;i<(((x->val-1)>T)?(x->val-1-T):0); i++)
if(hash[i]) count--;
for(i=(((x->val+T)>n)?n:(x->val+T));i<n; i++)
if(hash[i]) count--;
}
else if(T > size)
{
val=x->val;
x=x->parent;
while(x)
{
if(diff(val,x->val) <= T) count++;
x=x->parent;
}
}
else
{
for(i=((x->val-1)>T)?(x->val-1-T):0; i<(((x->val+T)>n)?n:(x->val+T)); i++)
{
if(hash[i])
{
//printf("%2d, 0x%x\n",i,hash[i]);
count++;
}
}
}
}
void solve()
{
Node *tmp=root;
Node *tmp1;
int i;
for(i=0;i<n;i++) hash[i]=NULL;
size=0;
while(tmp)
{
while(tmp->child_list)
{
hash[(tmp->val-1)%n]=tmp;
size++;
tmp=tmp->child_list;
}
countup(tmp);
tmp1=tmp;
tmp=tmp->parent;
if(tmp)// && (tmp->child_list == tmp1))
{
hash[(tmp->val-1)%n]=NULL;
size--;
tmp->child_list=tmp1->peer_next;
}
//printf("node = %3d (count = %d)\n",tmp1->val,count);
free(tmp1);
}
}
Node* allocate(unsigned int val)
{
Node *node=malloc(sizeof(Node));
memset(node,0,sizeof(Node));
node->val=val;
return node;
}
Node* insert(unsigned int val)
{
Node *tmp=hash[val%n];
if(!tmp)
{
return (hash[val%n]=allocate(val));
}
while(tmp)
{
if(tmp->val==val) return tmp;
if(!tmp->hash_next)
break;
tmp=tmp->hash_next;
}
return (tmp->hash_next=allocate(val));
}
void connect(Node *parent, Node *child)
{
if(!parent || !child) return;
/*if(!parent->child_list)
parent->child_list=child;
else
{
Node *peer=parent->child_list;
while(peer->peer_next) peer=peer->peer_next;
peer->peer_next=child;
}*/
child->peer_next=parent->child_list;
parent->child_list=child;
child->parent=parent;
}
void build(){
int i,a,b;
Node *parent,*child;
for(i=0;i<n-1;i++)
{
scanf("%d %d",&a,&b);
parent=insert(a);
child=insert(b);
//printf("%d %d\n",parent->val,child->val);
connect(parent,child);
/*if(!parent->parent)
root=parent;*/
}
root=hash[1];
while(root && root->parent) root=root->parent;
}
void print(Node *node, int level)
{
int i=level;
if(!node) return;
while(i--) printf(" ");
printf("%d (%d)\n",node->val,node->parent?node->parent->val:0);
node=node->child_list;
while(node)
{
print(node,level+1);
node=node->peer_next;
}
}
int main(){
count=0;
scanf("%d %d",&n,&T);
hash=malloc(n*sizeof(Node*));
memset(hash,0,n*sizeof(Node*));
if (!hash) return -1;
build();
//print(root, 0);
solve();
printf("%llu\n",count);
return 0;
}
Leave a comment below