Problem Statement
Geeks For Geeks – https://www.geeksforgeeks.org/problems/count-possible-triangles-1587115620/1
Given an integer array arr[]. Find the number of triangles that can be formed with three different array elements as lengths of three sides of the triangle. A triangle with three given sides is only possible if sum of any two sides is always greater than the third side.
Input: arr[] = [4, 6, 3, 7]
Output: 3
Explanation: There are three triangles possible [3, 4, 6], [4, 6, 7] and [3, 6, 7]. Note that [3, 4, 7] is not a possible triangle.
Input: arr[] = [10, 21, 22, 100, 101, 200, 300]
Output: 6
Explanation: There can be 6 possible triangles: [10, 21, 22], [21, 100, 101], [22, 100, 101], [10, 100, 101], [100, 101, 200] and [101, 200, 300]
My Approach
class Solution:
#Function to count the number of possible triangles.
def countTriangles(self, arr):
# code here
arr.sort()
n = len(arr)
cnt = 0
for itr in range(2, n):
left = 0
right = itr - 1
while left < right:
if arr[left] + arr[right] > arr[itr]:
cnt += right - left
right -= 1
else:
left += 1
return cnt
Syed Jafer K 