C Exercises: Count the number of triangles can be fromed from a given array

Last update on March 18 2025 13:21:17 (UTC/GMT +8 hours)

52. Count Triangles from Array

Write a program in C to count the number of triangles that can be formed from a given array.

Expected Output :
The given array is : 6 18 9 7 10
Number of possible triangles can be formed from the array is: 5

To count the number of triangles that can be formed from a given array, the program needs to check for every combination of three elements if they satisfy the triangle inequality theorem (the sum of any two sides must be greater than the third side). By iterating through all possible triplets in the array and validating this condition, the program can determine the number of valid triangles. This approach ensures all potential triangles are counted accurately.

Sample Solution:

C Code:

#include <stdio.h>
#include <stdlib.h>

// Comparison function for qsort
int compare(const void* one, const void* two) 
{
    return *(int*)one > *(int*)two; // Compare two integers
}

// Function to count the number of possible triangles that can be formed
int CountNumberOfTriangles(int *arr1, int arr_size) 
{
    int ctrTriangle = 0, i, j, k;
    qsort(arr1, arr_size, sizeof(int), compare); // Sort the array in ascending order

    for (i = 0; i < arr_size - 2; ++i) 
    {
        for (j = i + 1; j < arr_size; ++j) 
        {
            k = j + 1;
            // Check for triangles (arr1[i] + arr1[j]) > arr1[k]
            while (k < arr_size && (arr1[i] + arr1[j]) > arr1[k]) 
            {
                k++;
            }
            // Increment the count of triangles
            ctrTriangle += k - j - 1;
        }
    }
    return ctrTriangle;
}

int main() 
{
    int arr1[] = {6, 18, 9, 7, 10};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int i;

    // Print the original array
    printf("The given array is:  ");
    for (i = 0; i < n; i++)
    {
        printf("%d  ", arr1[i]);
    }
    printf("\n");

    // Calculate and print the number of possible triangles that can be formed from the array
    printf("Number of possible triangles that can be formed from the array is: %d\n",
           CountNumberOfTriangles(arr1, n));
    return 0;
}

Output:

The given array is :  6  18  9  7  10  
Number of possible triangles can be formed from the array is: 5

Flowchart:/p>

For more Practice: Solve these Related Problems:

Write a C program to count the number of triangles that can be formed from an array of side lengths using triple nested loops.
Write a C program to compute the number of valid triangles from an array after sorting the side lengths.
Write a C program to count triangles that can be formed using a two-pointer approach after sorting the array.
Write a C program to count the number of triangles and also list the triangle side combinations.

C Programming Code Editor:

Previous: Write a program in C to find the maximum circular subarray sum of a given array.
Next: Write a program in C to to print next greater elements in a given unsorted array. Elements for which no greater element exist, consider next greater element as -1.