Count Possible Triangles

Problem Statement

In count possible triangles problem we have given an array of n positive integers. Find the number of triangles that can be formed using three different elements of the array as the sides of a triangle.

Note: The condition of the triangle is the sum of two sides of a triangle is greater than the third side.

Example

Input

arr[] = {2, 3, 4, 5, 6, 7}

Output

13

Explanation

All the possible triplet 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 for Count Possible Triangles

Now we understand the problem statement clearly. So, without wasting too much time on the theory we directly move to the algorithm used for finding the number of triangles in the array.

a. Sort the given array in increasing order.

b. Take three positions i, j, and k

• i for the first element. i is from 0 to n – 3.
• j for the second element. i is from i + 1 to n – 2.
• k for the third element. k is from i+ 2 to n -1.

c. Find the rightmost 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.

Implementation

C++ Program for Count Possible Triangles

#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 n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<"Total number of Triangles can be formed is = "<<TrianglesCount(input_array,n);
    return 0;
}

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int TrianglesCount(int arr[], int n) 
    { 
        Arrays.sort(arr);
        int count = 0; 
        for (int i = 0; i < n - 2; ++i) { 
            int k = i + 2; 
            for (int j = i + 1; j < n; ++j) { 
                while (k < n && arr[i] + arr[j] > arr[k]) 
                    ++k; 
                if (k > j) 
                    count += k - j - 1; 
            } 
        } 
        return count; 
    } 
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int ans = TrianglesCount(arr,n);
        System.out.println("Total number of Triangles can be formed is = " + ans);
    } 
}

5
2 3 4 5 6

Total number of Triangles can be formed is = 7