Count the number of possible triangles CPP Method 1

Software Development
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[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)