Triangle Count from Array Program In Python

Count the number of valid triangles that can be formed from an array of integers where the sum of any two sides must be greater than the third side.

Understand the Problem

Problem Statement

An array of N integers is passed as the input to the program. The program must print the count of triangles that can be formed with the given integer values.

Note: Sum of any two sides in a triangle must be greater than the third side.

Constraints

3 ≤ N ≤ 500
1 ≤ Value of each integer ≤ 10000
All integers are positive
Array may contain duplicates

Examples

Example 1

Input

5
2 1 5 4 3

Output

Explanation

The valid triangles are: - (2, 3, 4): 2+3>4, 2+4>3, 3+4>2 - (2, 4, 5): 2+4>5, 2+5>4, 4+5>2 - (3, 4, 5): 3+4>5, 3+5>4, 4+5>3 Total count: 3

Example 2

Input

7
7 5 2 2 9 3 10

Output

Explanation

There are 10 valid triangle combinations that can be formed from these 7 numbers, satisfying the triangle inequality for all possible triplets.

Solution

#include <stdio.h>

int triangleCount(int arr[], int n) {
    int count = 0;
    
    // Check all possible triplets
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                // Check triangle inequality conditions
                if (arr[i] + arr[j] > arr[k] && 
                    arr[i] + arr[k] > arr[j] && 
                    arr[j] + arr[k] > arr[i]) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int arr[500];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    printf("%d", triangleCount(arr, n));
    
    return 0;
}

Time:O(n³) - Three nested loops iterating through all possible triplets

Space:O(1) - Only using a constant amount of extra space for variables

Approach:

1. The triangleCount function takes an array and its size as parameters
2. Uses three nested loops to generate all possible combinations of three elements
3. For each triplet, checks if it satisfies the triangle inequality conditions
4. Counts valid triangles and returns the total
5. The main function reads input, calls the function, and prints the result

Visual Explanation

Loading diagram...

All Problems