- Prepare
- Algorithms
- Search
- Similar Pair
- Discussions
Similar Pair
Similar Pair
+ 0 comments Can we solve this puzzle with the help of AI technology. دعاء لرجوع الزوج
+ 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 comments Thanks, that is a very good idea. In fact where we keep a record of deleted values. powerful revenge spells
+ 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 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.
Sort 80 Discussions, By:
Please Login in order to post a comment