# Count possible triangles

## In the given array of positive integers. Find the number of triangles can be formed using three different elements of the array as the sides of a triangle.

Condition: sum of two sides of a triangle is greater than the third side.

### Example

Input array: [2, 3, 4, 5, 6, 7]
Output: 13

### Triangles possible are

{2, 3, 4}, {2, 4, 5}, {2, 5, 6},{2, 6, 7}, {3, 4, 5}, {3, 4, 6},{3, 5, 6}, {3, 5, 7}, {3, 6, 7}, {4, 5, 6}, {4, 5, 7}, {4, 6, 7}, {5, 6, 7}

## Algorithm

Time complexity: O(n2)

a. Sort the given array in increasing order.

b. Take three positions i, j and k
1)    i for first element. i is from 0 to n - 3
2)    j for second element. i is from i + 1 to n - 2
3)    K for third element. k is from i+ 2 to n -1

c. Find the right most element which is smaller than the sum of the current i and j by moving k.
d. K – j – 1 is the count of triangles, for current i and j.
e. Add it to the count and increment i, j.

## C++ Program

``````#include <bits/stdc++.h>

using namespace std;

int compare(const void* a, const void* b)
{
return *(int*)a > *(int*)b;
}

int TrianglesCount(int array[], int n)
{
qsort(array,n,sizeof(array[0]),compare);
int count = 0;
for (int i = 0; i < n-2; ++i)
{
for (int j = i+1; j < n; ++j)
{
int k = j+1;
while (k < n && array[i] + array[j] > array[k])
{
k = k + 1;
}
count = count + k - j - 1;
}
}
return count;
}

//Main function
int main()
{
int input_array[] =   {2, 3, 4, 5, 6};
int size = sizeof(input_array)/sizeof(int);
cout<<"Total number of Triangles can be formed is = "<<TrianglesCount(input_array,size);
return 0;
}``````

Scroll to Top