Given a 2D matrix g contains only 1 and 0, count the number of triangles in it.
Take 3 index i,j,k (0<=i,j,k<n). {i,j}, {j,k}, {k,i} will form a triangle if i!=j and i!=k and j!=k and g[i][j]=1 and g[j][k]=1 and g[k][i]=1.
Example 1:
Input:
N=4
graph[][]={{0, 0, 1, 0}, 
           {1, 0, 0, 1},
           {0, 1, 0, 0}, 
           {0, 0, 1, 0}}
Output:
2
Explanation;
Triangle 1: {{0,2}, {2,1}, {1,0}}
graph[][]={{0, 0, 1, 0},
           {1, 0, 0, 1},
           {0, 1, 0, 0},
           {0, 0, 1, 0}}.  
Triangle 2: {{1,3}, {3,2}, {2,1}}
graph[][]={{0, 0, 1, 0},
           {1, 0, 0, 1},
           {0, 1, 0, 0},
           {0, 0, 1, 0}}. 
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function numberOfTriangles() which takes the 2D matrix g[][], it's number of nodes N as input parameters and returns the number of triangles in it.
 
Expected Time Complexity: O(N*N*N)
Expected Auxiliary Space: O(1)
 
Constraints:
1<=N<=100
0<=g[i][j]<=1

Source: geeksforgeeks | Difficulty: EASY

Starter code: from typing import List





class Solution:

    def numberOfTriangles(self, n : int, g : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def numberOfTriangles(self, n: int, g: List[List[int]]) -> int:
		cnt = 0
		for i in range(n):
			for j in range(n):
				for k in range(n):
					if (i != j and j != k and (i != k)) and g[i][j] == 1 and (g[j][k] == 1) and (g[k][i] == 1):
						cnt += 1
		return cnt // 3


from typing import List

class Solution:

	def numberOfTriangles(self, n: int, g: List[List[int]]) -> int:
		r = len(g)
		c = len(g[0])
		count = 0
		for i in range(r):
			for j in range(c):
				for k in range(c):
					if i != j and j != k and (i != k):
						if g[i][j] == 1 and g[j][k] == 1 and (g[k][i] == 1):
							count += 1
		return count // 3


from typing import List
from collections import deque

class Solution:

	def numberOfTriangles(self, n: int, g: List[List[int]]) -> int:
		nodes = len(g)
		count_Triangle = 0
		for i in range(nodes):
			for j in range(nodes):
				for k in range(nodes):
					if i != j and i != k and (j != k) and g[i][j] and g[j][k] and g[k][i]:
						count_Triangle += 1
		return count_Triangle // 3


from typing import List

class Solution:

	def numberOfTriangles(self, n: int, g: List[List[int]]) -> int:
		count_traingle = 0
		for i in range(n):
			for j in range(n):
				for k in range(n):
					if i != j and i != k and (j != k) and g[i][j] and g[j][k] and g[k][i]:
						count_traingle += 1
		return count_traingle // 3

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		g = IntMatrix().Input(n, n)
		obj = Solution()
		res = obj.numberOfTriangles(n, g)
		print(res)


from typing import List

class Solution:

	def numberOfTriangles(self, n: int, g: List[List[int]]) -> int:
		if n < 3:
			return 0
		else:
			res = 0
			for i in range(0, n - 2):
				for j in range(i + 1, n - 1):
					for k in range(j + 1, n):
						p1 = g[i][j] + g[j][k] + g[k][i]
						p2 = g[i][k] + g[k][j] + g[j][i]
						if p1 == 3:
							res = res + 1
						if p2 == 3:
							res = res + 1
			return res