Count the number of possible triangles CPP Method 2

Software Development
#1

Method 2: This is a tricky and efficient approach to reduce the time complexity from O(n^3) to **O(n^2)**where two sides of the triangles are fixed and the count can be found using those two sides.

  • Approach: First sort the array in ascending order. Then use two loops. The outer loop to fix the first side and inner loop to fix the second side and then find the farthest index of the third side (greater than indices of both sides) whose length is less than sum of the other two sides. So a range of values third sides can be found, where it is guaranteed that its length if greater than the other individual sides but less than the sum of both sides.

  • Algorithm: Let a, b and c be three sides. The below condition must hold for a triangle (sum of two sides is greater than the third side)
    i) a + b > c
    ii) b + c > a
    iii) a + c > b
    Following are steps to count triangle.

    1. Sort the array in ascending order.
    2. Now run a nested loop. The outer loop runs from start to end and the innner loop runs from index + 1 of the first loop to the end. Take the loop counter of first loop as i and second loop as j. Take another variable k = i + 2
    3. Now there is two pointers i and j, where array[i] and array[j] represents two sides of the triangles. For a fixed i and j, find the count of third sides which will satisfy the conditions of a triangle. i.e find the largest value of array[k] such that array[i] + array[j] > array[k]
    4. So when we get the largest value, then the count of third side is k – j, add it to the total count.
    5. Now sum up for all valid pairs of i and j where i < j

  • Implementation:

  • C++

// C++ program to count number of triangles that can be

// formed from given array

#include <bits/stdc++.h>

using namespace std;

/* Following function is needed for library function

qsort(). Refer

http:// www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */

int comp( const void * a, const void * b)

{

return *( int *)a > *( int *)b;

}

// Function to count all possible triangles with arr[]

// elements

int findNumberOfTriangles( int arr[], int n)

{

// Sort the array elements in non-decreasing order

qsort (arr, n, sizeof (arr[0]), comp);

// Initialize count of triangles

int count = 0;

// Fix the first element. We need to run till n-3

// as the other two elements are selected from

// arr[i+1...n-1]

for ( int i = 0; i < n - 2; ++i) {

// Initialize index of the rightmost third

// element

int k = i + 2;

// Fix the second element

for ( int j = i + 1; j < n; ++j) {

// Find the rightmost element which is

// smaller than the sum of two fixed elements

// The important thing to note here is, we

// use the previous value of k. If value of

// arr[i] + arr[j-1] was greater than arr[k],

// then arr[i] + arr[j] must be greater than k,

// because the array is sorted.

while (k < n && arr[i] + arr[j] > arr[k])

++k;

// Total number of possible triangles that can

// be formed with the two fixed elements is

// k - j - 1. The two fixed elements are arr[i]

// and arr[j]. All elements between arr[j+1]/ to

// arr[k-1] can form a triangle with arr[i] and arr[j].

// One is subtracted from k because k is incremented

// one extra in above while loop.

// k will always be greater than j. If j becomes equal

// to k, then above loop will increment k, because arr[k]

// + arr[i] is always greater than arr[k]

if (k > j)

count += k - j - 1;

}

}

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^2).
      The time complexity looks more because of 3 nested loops. It can be observed that k is initialized only once in the outermost loop. The innermost loop executes at most O(n) time for every iteration of the outermost loop, because k starts from i+2 and goes up to n for all values of j. Therefore, the time complexity is O(n^2).
    • Space Complexity: O(1).
      No extra space is required. So space complexity is constant