HackerRank Similar Pair Problem Solution

HackerRank Similar Pair Problem Solution

Yashwant Parihar,

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

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

Leave a Reply