Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank Similar Pair Problem Solution

HackerRank Similar Pair Problem Solution

Posted on May 13, 2023May 13, 2023 By Yashwant Parihar No Comments on HackerRank Similar Pair Problem Solution

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:

  1. node a is the ancestor of node b
  2. 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

4

Explanation

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.

HackerRank Similar Pair Problem Solution
HackerRank Similar Pair Problem Solution

Table of Contents

  • Similar Pair C Solution
  • Similar Pair C++ Solution
  • Similar Pair C Sharp Solution
  • Similar Pair Java Solution
  • Similar Pair JavaScript Solution
  • Similar Pair Python Solution

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)
c, C#, C++, HackerRank Solutions, java, javascript, python Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Task Scheduling Problem Solution
Next Post: HackerRank Absolute Element Sums Solution

Related Posts

HackerRank Two Robots Problem Solution HackerRank Two Robots Problem Solution c
HackerRank Black and White Tree Problem Solution HackerRank Black and White Tree Solution c
HackerRank Find Strings Problem Solution HackerRank Find Strings Problem Solution c
HackerRank Synchronous Shopping Problem Solution HackerRank Synchronous Shopping Solution c
HackerRank Solve Me First Problem Solution HackerRank Solve Me First Problem Solution c
HackerRank CamelCase Problem Solution HackerRank CamelCase Problem Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme