Home » Interview » Array Interview Questions » Count possible triangles

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