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.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. The Value of Friendship
  5. Discussions

The Value of Friendship

Sort by

recency

|

25 Discussions

|

  • michal_suchowol1
     + 0 comments

    It would be nice if there was at least a single non-trivial test to check understanding of the problem...

  • yashparihar729
     + 0 comments

    Here is my solution in java, javascript, python, C, C++, Csharp HackerRank The Value of Friendship Solution

  • mineman1012221
     + 0 comments

    Here is the solution of The Value of Friendship Click Here

  • bhautik4avenger4
     + 1 comment

    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.

  • sebastinmangalan
     + 1 comment

    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)