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. Graph Theory
  4. The Value of Friendship
  5. Discussions

The Value of Friendship

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 22 Discussions, By:

recency

Please Login in order to post a comment

  • bhautik4avenger4
    7 months ago+ 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|
    Permalink
  • sebastinmangalan
    8 months ago+ 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|
    Permalink
  • pereiraripson
    1 year ago+ 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|
    Permalink
  • alex_fotland
    2 years ago+ 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|
    Permalink
  • sagarthecoder
    3 years ago+ 0 comments

    I have solved it using dfs.
    Good Problem by the way

    -3|
    Permalink
Load more conversations

Need Help?


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