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.
The Value of Friendship
The Value of Friendship
+ 0 comments https://zeroplusfour.com/the-value-of-friendship-hackerrank-solution/
Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.
+ 0 comments jt_112's solution in Python3
parent={} no_of_friends={} def findparent(x): if parent[x] == x: return x parent[x] = findparent(parent[x]) return parent[x] def value (n): t1=n*(n+1)*(2*n+1) t1/=6 t2=n*(n+1) t2/=2 return t1-t2 def valueOfFriendsship(n,m, friendships): # Write your code here total, current, ans =0,0,0 for i in range(1,n+1): parent[i] = i no_of_friends[i] = 1 for i in range(m): u,v=friendships[i][0],friendships[i][1] pu,pv = findparent(u),findparent(v) if pu != pv: parent[pv] = pu no_of_friends[pu] += no_of_friends[pv] p=[] for i in range(1,n+1): if(parent[i] == i): p.append(no_of_friends[i]) p.sort(reverse=True) for i in range(len(p)): current+=(p[i]-1) ans +=value(p[i])+total*(p[i]-1) total+=(p[i] * (p[i]-1)) ans+=((m-current)*total) return int(ans)
+ 0 comments how do i optimise this further only 1 test case passes with this one` def valueOfFriendsship(n, friendships): p=[i for i in range(1,n+1)] f=[0 for i in range(n)]
def findparent(n): if p[n-1]==n: return n else: return findparent(p[n-1]) def union(a,b): x=findparent(a) y=findparent(b) if x!=y: if f[a-1]>f[b-1]: p[b-1]=x a=f[a-1]+1 for i in range(len(p)): if p[i]==x: f[i]=a else: p[a-1]=y a=f[b-1]+1 for i in range(len(p)): if p[i]==y: f[i]=a s=0 for i in friendships: union(i[0],i[1]) s+=sum(f) return s
`
+ 0 comments This is a pretty simple combinatorics problem. HackerRank seems to base the difficulty levels of problems on the assumption that we don't know math.
+ 0 comments I have solved it using dfs.
Good Problem by the way
Load more conversations
Sort 22 Discussions, By:
Please Login in order to post a comment