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.

Algorithm working

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;
}
Try It

 


Next > < Prev
Scroll to Top