# Count the number of possible triangles CPP Method 1

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:

1. 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.
2. 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
3. if all three conditions match, increase the count.
4. 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);`

` ` `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)