In this post, we will solve HackerRank Similar Pair Problem Solution.
A pair of nodes, (a, b), is a similar pair if the following conditions are true:
- node a is the ancestor of node b
- abs(a – b) ≤ k
Given a tree where each node is labeled from 1 to n, find the number of similar pairs in the
tree.
We have the following pairs of ancestors and dependents:
Pair abs(a-b) Pair abs(a-b) 1,2 1 3,4 1 1,3 2 3,5 2 1,4 3 3,6 3 1,5 4 1,6 5
If k = 3 for example, we have 6 pairs that are similar, where abs (a – b) ≤ k.
Function Description
Complete the similarPair function in the editor below. It should return an integer that represents the number of pairs meeting the criteria.
similarPair has the following parameter(s):
- n: an integer that represents the number of nodes
- k: an integer
- edges: a two dimensional array where each element consists of two integers that represent connected node numbers
Input Format
The first line contains two space-separated integers n and k, the number of nodes and the similarity threshold.
Each of the next n – 1 lines contains two space-separated integers defining an edge connecting nodes p[i] and c[i], where node p[i] is the parent to node c[i].
Output Format
Print a single integer denoting the number of similar pairs in the tree.
Sample Input
5 2
3 2
3 1
1 4
1 5
Sample Output
4Explanation
The similar pairs are (3,2), (3, 1), (3, 4), and (3, 5), so we print 4 as our answer. Observe that (1, 4) and (1, 5) are not similar pairs because they do not satisfy abs (a – b)k for k = 2.
Similar Pair C Solution
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.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;
}Similar Pair C++ Solution
#include<bits/stdc++.h>
using namespace std;
long long int bit[100005];
long long int k;
long long int n;
long long int root;
vector<vector<long long int> > edg(100005);
long long int ans = 0;
void update(int pos,int val) {
while(pos<=n) {
bit[pos]+=val;
pos+=(pos & -pos);
}
}
long long int read(int pos) {
long long int sum = 0;
while(pos>0) {
sum+=bit[pos];
pos-=(pos & -pos);
}
return sum;
}
void calculate(int pos) {
long long int l=0,r=0;
l = read(pos-k-1);
if(pos+k<=n) {
r = read(pos+k);
} else {
r = read(n);
}
//cout << pos << " "<< l <<" "<<r <<"\n";
ans += (r-l);
update(pos,1);
for(int i=0;i<edg[pos].size();i++) {
calculate(edg[pos][i]);
}
update(pos,-1);
}
int main() {
memset(bit,0,sizeof(bit));
cin>>n>>k;
int src,des;
for(int i=0;i<n-1;i++) {
cin>>src>>des;
edg[src].push_back(des);
if(i==0)
root = src;
}
calculate(root);
cout << ans <<"\n";
return 0;
}Similar Pair C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static int n;
static int[] runningTotal;
static void Main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
int[] input = Console.ReadLine().Split().Select(item => int.Parse(item)).ToArray();
n = input[0];
int k = input[1];
Node[] nodes = new Node[n];
Node root = null;
for (int i = 0; i < n - 1; i++)
{
input = Console.ReadLine().Split().Select(item => int.Parse(item)).ToArray();
int parentId = input[0] - 1;
Node parent = nodes[parentId];
if (parent == null)
{
parent = new Node() { Id = parentId };
nodes[parentId] = parent;
}
if (i == 0)
{
root = parent;
}
int childId = input[1] - 1;
Node child = nodes[childId];
if (child == null)
{
child = new Node() { Id = childId };
nodes[childId] = child;
}
if (parent.Children == null)
{
parent.Children = new HashSet<Node>();
}
parent.Children.Add(child);
}
long total = 0;
runningTotal = new int[n];
Stack<Node> dfs = new Stack<Node>();
dfs.Push(root);
Increment(root.Id);
while (dfs.Count != 0)
{
Node node = dfs.Peek();
if ((node.Children != null) && (node.Children.Count != 0))
{
Node child = node.Children.First();
node.Children.Remove(child);
int includeBound = child.Id + k;
int upper = Sum(includeBound);
int excludeBound = child.Id - k - 1;
int lower = Sum(excludeBound);
total += (upper - lower);
if (child.Children != null)
{
dfs.Push(child);
Increment(child.Id);
}
}
else
{
dfs.Pop();
Decrement(node.Id);
}
}
Console.WriteLine(total);
}
class Node
{
public int Id;
public HashSet<Node> Children;
}
static int Sum(int i)
{
if (i >= n) { i = n - 1; }
else if (i < 0) { return 0; }
i++;
int result = 0;
while (i > 0)
{
result += runningTotal[i-1];
i -= (i & -i);
}
return result;
}
static void Increment(int i)
{
i++;
while (i <= n)
{
runningTotal[i-1]++;
i += (i & -i);
}
}
static void Decrement(int i)
{
i++;
while (i <= n)
{
runningTotal[i-1]--;
i += (i & -i);
}
}
}Similar Pair Java 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;
}
}
}Similar Pair JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function (inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function () {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'similarPair' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. INTEGER k
* 3. 2D_INTEGER_ARRAY edges
*/
function similarPair(n, k, edges) {
// Write your code here
// tree node
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}
addChild(node) {
this.children.push(node);
}
}
let tree = new Array(n).fill(null);
let head = new TreeNode(edges[0][0] - 1);
tree[head.value] = head;
// forming the tree...
for (let [parent, child] of edges) {
let node = new TreeNode(child - 1);
tree[child - 1] = node;
tree[parent - 1].addChild(node);
}
// forming the tree over...
// implement dfs to find similar pairs
let biTree = new Array(n+1).fill(0);
let getTree = (index) => {
let sum = 0;
while (index > 0) {
sum += biTree[index];
index -= index & (-index);
}
return sum;
};
let updateTree = (index, value) => {
index ++;
while (index <= n) {
biTree[index] += value;
index += index & (-index);
}
}
let similarPairs = 0;
let stack = [];
stack.push(head);
updateTree(head.value, 1);
while (stack.length) {
let currentNode = stack[stack.length - 1];
if (currentNode.children.length) {
let childNode = currentNode.children.pop();
updateTree(childNode.value, 1);
stack.push(childNode);
} else {
let childNode = stack.pop();
updateTree(childNode.value, -1);
let count1 = getTree(Math.min(currentNode.value + k + 1, n));
let count2 = 0;
if (currentNode.value - k >= 0) {
count2 = getTree(Math.max(currentNode.value - k, 0));
}
let count = count1 - count2;
similarPairs += count;
// break;
}
}
return similarPairs;
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');
const n = parseInt(firstMultipleInput[0], 10);
const k = parseInt(firstMultipleInput[1], 10);
let edges = Array(n - 1);
for (let i = 0; i < n - 1; i++) {
edges[i] = readLine().replace(/\s+$/g, '').split(' ').map(edgesTemp => parseInt(edgesTemp, 10));
}
const result = similarPair(n, k, edges);
ws.write(result + '\n');
ws.end();
}Similar Pair Python Solution
#!/bin/python3
import sys
def update(fw, i, d):
n = len(fw)
while i <= n:
fw[i] += d
i += i & -i
def diff(fw, a, b):
u = 0
while b:
u += fw[b]
b -= b & -b
while a:
u -= fw[a]
a -= a & -a
return u
def similar(line):
n, K = map(int, next(line).split())
root = set(range(1, n - 1))
tree = {}
for x in range(n - 1):
a, b = map(int, next(line).split())
root -= {b}
tree[a] = tree.get(a, []) + [b]
root = list(root)
stack = [iter(root)]
visited = [True] * (n + 1)
fw = [0] * (n + 2)
cnt = 0
while stack:
for id in stack[-1]:
if visited[id]:
cnt += diff(fw, max(0, id - K - 1), min(n, id + K))
visited[id] = False
if id in tree:
root.append(id)
stack.append(iter(tree[id]))
update(fw, id, 1)
break
else:
update(fw, root.pop(), -1)
stack.pop()
print(cnt)
similar(sys.stdin)
