HackerEarth Counting triplets problem solution

YASH PAL, 31 July 202416 February 2026

In this HackerEarth Counting triplets problem solution You are given an undirected, complete graph G that contains N vertices. Each edge is colored in either white or black. You are required to determine the number of triplets (i,j,k) (1 <= i < j < k <= N) of vertices such that the edges (i,j), (j,k), (i,k) are of the same color.

There are M white edges and N(N – 1)/ 2 – M black edges.

HackerEarth Counting triplets problem solution

HackerEarth Counting triplets problem solution.

import numpy as np
n,m=map(int,input().split())
edge={}
deg=np.zeros(n).astype(np.int)
#assert n<=2000,exit(1)
for i in range(m):
    a,b=map(int,input().split())
    assert a!=b,exit(1)
    assert max(a,b)<=n and min(a,b)>=1, exit(1)
    if a>b:
        a,b=b,a
    if (a,b) in edge:
        exit(1)
    edge[(a,b)]=True
    deg[a-1]+=1
    deg[b-1]+=1
ans=0
for i in range(n):
    ans+=deg[i]*(n-deg[i]-1)
#print(ans)
ALL=n*(n-1)*(n-2)/6
ALL-=ans/2
print(int(ALL))

Second solution

n,m = map(int,input().split())
d = [0] * (n + 5)
for i in range(m):
    x,y = map(int,input().split())
    d[x] += 1
    d[y] += 1
ans = 0
for i in range(1,n + 1):
    ans += d[i] * (n - 1 - d[i])
print((n * (n - 1) * (n - 2) // 3 -  ans) // 2)

coding problems solutions HackerEarth HackerEarth

Leave a Reply