Home » Technical Interview Questions » Array Interview Questions » Count Possible Triangles

Count Possible Triangles


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.

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 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;
}
Total number of Triangles can be formed is = 7
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup