We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Similar Pair
  5. Discussions

Similar Pair

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 80 Discussions, By:

recency

Please Login in order to post a comment

  • tildanealey
    5 months ago+ 0 comments

    Can we solve this puzzle with the help of AI technology. دعاء لرجوع الزوج

    0|
    Permalink
  • bhautik4avenger4
    7 months ago+ 0 comments

    https://zeroplusfour.com/similar-pair-hackerrank-solution/

    Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.

    0|
    Permalink
  • johnpitts9342
    1 year ago+ 0 comments

    Thanks, that is a very good idea. In fact where we keep a record of deleted values. powerful revenge spells

    0|
    Permalink
  • rajmohit389
    1 year ago+ 0 comments

    this is my final code all test cases passed except two if anyone can help me in it.

    #include <bits/stdc++.h>
    using namespace std;
    vector<int> adj[100001];
    long long pairs=0;
    int k;
    
    void dfs(int x,vector<int>parent){
        parent.push_back(x);
        for(auto i:adj[x]){
            int j=0;
            while(j<parent.size()){
                if(abs(i-parent[j])<=k){
                    pairs++;
                }
                j++;
            }
            if(!adj[i].empty()){
                dfs(i,parent);
            }
        }
    }
    
    int main()
    {
        int n;
        cin>>n;
        cin>>k;
        long long sum=(n*(n+1))/2;
        for(int i=0;i<n-1;i++){
            int u,v;
            cin>>u>>v;
            sum-=v;
            adj[u].push_back(v);
        }
        int root=(int)sum;
        vector<int>parent;
        dfs(root,parent);
        cout<<pairs<<endl;
        return 0;
    }
    
    0|
    Permalink
  • crankyinmv
    2 years ago+ 0 comments

    It's definitely worth the time to learn about Fenwick trees. These will allow you to add items, remove items, and count a range of items in O(log(n)) time. After that it's fairly straightforward.

    This is the approach I took:
    - Built the adjacency list from the directed edges.
    - Found the root using a math trick: n(n+1)/2 - sum(edges[i][1]).
    - Created a FT starting with an array of n nodes of 0.
    - DFS through the tree:
    -- Count the nodes in the tree between current-k and current+k (truncated to 1..n ).
    -- If the current node isn't a leaf:
    --- Set the current node.
    --- Add the counts from the children.
    --- Clear the current node.

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy