Method 1(Brute Force)
-
Approach: The brute force method is to run three loops and keep track of the number of triangles possible so far. The three loops select three different values from an array. The innermost loop checks for the triangle property which specifies the sum of any two sides must be greater than the value of the third side).
-
Algorithm:
- Run three nested loops each loop starting from the index of the previous loop to end of array i.e run first loop from 0 to n, loop j from i to n and k from j to n.
- Check if array[i] + array[j] > array[k], array[i] + array[k] > array[j], array[k] + array[j] > array[i], i.e. sum of two sides is greater than the third
- if all three conditions match, increase the count.
- Print the count
-
Implementation:
-
C++
// C++ code to count the number of
// possible triangles using brute
// force approach
#include <bits/stdc++.h>
using
namespace
std;
// Function to count all possible
// triangles with arr[] elements
int
findNumberOfTriangles(
int
arr[],
int
n)
{
// Count of triangles
int
count = 0;
// The three loops select three
// different values from array
for
(
int
i = 0; i < n; i++) {
for
(
int
j = i + 1; j < n; j++) {
// The innermost loop checks for
// the triangle property
for
(
int
k = j + 1; k < n; k++)
// Sum of two sides is greater
// than the third
if
(
arr[i] + arr[j] > arr[k]
&& arr[i] + arr[k] > arr[j]
&& arr[k] + arr[j] > arr[i])
count++;
}
}
return
count;
}
// Driver code
int
main()
{
int
arr[] = { 10, 21, 22, 100, 101, 200, 300 };
int
size =
sizeof
(arr) /
sizeof
(arr[0]);
cout
<<
"Total number of triangles possible is "
<< findNumberOfTriangles(arr, size);
return
0;
}
Output:
Total number of triangles possible is 6
-
Complexity Analysis:
- Time Complexity: O(N^3) where N is the size of input array.
- Space Complexity: O(1)