Program to Count Number of Possible Triangles using Array Elements

  • Write a program to find the number of possible triangles from any three elements of array.
  • Count number of possible triangles from array elements using sorting.

Given an integer array of size N. We have to count total number of possible triangles which can be formed using any three elements of array as sides of triangle. Here we are going to use the side sum property of triangle to determine the possibility of a triangle for three given side lengths.

The sum of any two sides of a triangle must be greater than the third side.
Let A, B and C be the length of three sides of a triangle. Then A+B > C, B+C > A and A+C > B.
For Example :
Input Array : 4 22 7 5 10
Output :
Triangle Count : 3
4 7 5
4 7 10
7 5 10

Let inputArray be an integer array of size N.

Brute Force Method
  • Using three for loop, generate all possible combination of triplet and check whether these three elements satisfy above mentioned condition or not.
Time Complexity : O(n3)
By Sorting Input Array
Algorithm to count number of possible triangle from array elements using sorting.
  • Sort inputArray using any O(nLogn) average time algorithm like quick sort or merge sort.
  • Initialize first and second to 0 and 1 index.
  • Using two for loop, generate all possible pairs of elements, inputArray[first] and inputArray[second]. Both corresponds to two sides of triangle.
  • inputArray[first] and inputArray[second] can form triangle with inputArray[third], if inputArray[first] + inputArray[second] > inputArray[third].
  • Initialize third = second+1. Traverse inputArray until inputArray[first] + inputArray[second] > inputArray[third]. Now, third-second+1 gives the count of all possible triangles having inputArray[first] and inputArray[second] as two sides.

C program to count number of triangles using array elements using sorting

#include <stdio.h>
#include <stdlib.h>
 
/* This function will be used as a comparator 
function by qsort function */
int compare(const void* one, const void* two) {
    return *(int*)one > *(int*)two;
}
 
/* Returns total number of possible triangles */
int getTotalTriangles(int *array, int size) {
    int triangleCount = 0, i, j, k;
    /* sort input array */
    qsort(array, size, sizeof(int), compare);

    /* Using two for loops, fix first two sides of a triangle
  and then try to find the count of all such elements 
  which is greater than the sum of both sides. */
    for(i = 0; i < size-2; ++i) {
        /* Iteratr for second element */
        for (j = i+1; j < size; ++j) {
            /* Initialize third element */
            k = j +1;
            /* Three elemets of an array can form a triangle if, 
  sum of any two element is more than third element */
            while (k < size && (array[i] + array[j])> array[k]) {
             k++;
     }
            
            /* Total number of possible triangle with array[i] 
  and array[j] as teo sides are k - j -1 */
            
            triangleCount += k - j - 1;
        }
    }
 
    return triangleCount;
}

int main() {
    int array[5] =  {4, 22, 7, 5, 10};
 
    printf("Total Possible Triangles : %d\n",
           getTotalTriangles(array, 5));
 
    return 0;
}
Output
Total Possible Triangles : 3
Posted by
Labels: ,