Submit | All submissions | Best solutions | Back to list |
EIUTRIGLE - Number of triangles |
Given an unsorted array of positive integers. Find the number of triangles that can be formed with three different array elements as three sides of triangles. For a triangle to be possible from 3 values, the sum of any two values (or sides) must be greater than the third value (or third side).
For example, if the input array is {4, 6, 3, 7}, the output should be 3. There are three triangles possible {3, 4, 6}, {4, 6, 7} and {3, 6, 7}. Note that {3, 4, 7} is not a possible triangle.
Input
The first line is an integer N
The next line contains N integers corresponding to the length of one side of a triangle.
The first line is an integer N
The next line contains N integers corresponding to the length of one side of a triangle.
Output
The number of possible triangles
Testcase:
https://drive.google.com/file/d/1ESqzd5Ad7URl_ThfpN3UKMpiCzwN3mEd/view?usp=share_link
Example
Input: 5
1 4 3 6 2 Output: 2