Home »
Data Structure »
Array Data Structure
Count the number of possible triangles
C++ implementation to count the number of possible triangles.
Submitted by Vikneshwar GK, on February 06, 2022
Consider an integer array of size n which is unsorted. The task at hand is to find the number of triangles that can be formed using any 3 elements from the array.
Note: The condition for a triangle to exist is that the sum of any two sides must be greater than the third side, that is, A+B>C
Example:
Input:
array= {6, 1, 2, 7, 4}
Output:
Total number of triangles possible: 2
Input:
array= {2, 4, 8, 5, 6}
Output:
Total number of triangles possible: 6
Solution 1: Brute force
This is the inefficient method, that is, to try out every possible combination and check the triangle condition for that combination. It uses 3 loops to find the 3 elements.
- Iterate through the array using 3 loops, each loop starts with the next element of the previous loop's starting index. For example, if i=0, then j=i+1 and k=j+1
- Check for the triangle condition. If array[i]+array[j]>array[k], then increment the counter
- Print the counter
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
// Function to count all possible
// triangles with arr[] elements
// Function to count all possible triangles
int triangleCount(int array[], int length)
{
// counter
int count = 0;
// 3 loops to hold 3 sides
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
for (int k = j + 1; k < length; k++)
// check triangle condition
if (
array[i] + array[j] > array[k]
&& array[i] + array[k] > array[j]
&& array[k] + array[j] > array[i])
count++;
}
}
return count;
}
// Main function
int main()
{
int array[100], N, x;
cout << "Enter Number of elements: ";
cin >> N;
for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
cout << "Total number of triangles possible: " << triangleCount(array, N);
return 0;
}
Output:
Enter Number of elements: 5
Enter element 1:2
Enter element 2:4
Enter element 3:8
Enter element 4:5
Enter element 5:6
Total number of triangles possible: 6
Time Complexity: O(n3), where n is the length of the array
Solution 2: Sort and Search
This is a comparatively efficient method that involves sorting the array first. Then select the first 2 elements and find the third element which is the least element that fails the triangle condition with the first two elements. Then we can say that the following items after 3rd element will also fail the triangle condition. Therefore only the elements before it will satisfy the triangle condition.
- Ascendingly sort the array
- Iterate through a nested loop where the outer loop i runs 0 to n-1 and inner loop j runs from i+1 to n. At the same time assign i+2 to variable k
- Now that we have two pointers that is i and j, increment the k until the triangle condition fails
- Add k-j to the total count
- Now repeat this for all valid pairs of i and j, where i<j
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
// compare function to be used in sort
int comp(const void* element1, const void* element2)
{
return *(int*)element1 > *(int*)element2;
}
// Funtion to count all possible triangles
int triangleCount(int array[], int length)
{
// sort the array
qsort(array, length, sizeof(array[0]), comp);
// Initialize count of triangles
int count = 0;
//outer loop to iterate from 0 to length-2
for (int i = 0; i < length - 2; ++i) {
// Initialize k
int k = i + 2;
// inner loop to iterate from i+1 to n-1
for (int j = i + 1; j < length; ++j) {
// check the triangle condition using k as the third side
while (k < length && array[i] + array[j] > array[k])
++k;
// Since k points to the third smallest element that fails the
// triangle condition, we ignore the elements that follows it
// therefore add the elements that are from j to k
// which is k-j+1
if (k > j)
count += k - j - 1;
}
}
return count;
}
// main function
int main()
{
int array[100], N, x;
cout << "Enter Number of elements: ";
cin >> N;
for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
cout << "Total number of triangles possible: " << triangleCount(array, N);
return 0;
}
Output:
Enter Number of elements: 5
Enter element 1:6
Enter element 2:1
Enter element 3:2
Enter element 4:7
Enter element 5:4
Total number of triangles possible: 2
Time Complexity: O(n2), where n is the length of the array
Solution 3: Using Two Pointers
Like the previous approach, this also involves sorting the array. We use a nested loop and try to find an upper and lower bound, using an index. Then we use all the elements in that range, with the fixed index, to form the triangle.
- Sort the array in ascending order
- Assign a left and a right pointer to 0 and n-1 and an index variable to iterate from right to left
- Iterate through the array using index variable from n-1 to 1 while updating the right pointer to index-1 for each iteration
- If the values at the left, right, and index satisfy the triangle condition, then all the elements between left and right will also satisfy the condition with index, since the array is sorted
- Decrement the right and repeat these steps until right is less than left
- Then increment left and repeat the steps until left is greater than right
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
// Function to count all possible triangles
void triangleCount(int array[], int length)
{
sort(array, array + length);
int count = 0;
for (int i = length - 1; i >= 1; i--) {
int left = 0, right = i - 1;
while (left < right) {
if (array[left] + array[right] > array[i]) {
// if left and right elements satisfy the condition,
// then the elements in between will also satify
// it can calculated by subtracting right and left
count += right - left;
// checking for more possible solutions
right--;
}
else
// if not, increment left
left++;
}
}
cout << "No of possible solutions: " << count;
}
// main function
int main()
{
int array[100], N;
cout << "Enter Number of elements: ";
cin >> N;
for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
triangleCount(array, N);
return 0;
}
Output:
Enter Number of elements: 5
Enter element 1:4
Enter element 2:3
Enter element 3:5
Enter element 4:7
Enter element 5:6
No of possible solutions: 9
Time Complexity: O(n2), where n is the length of the array