Array ( [0] => [1] => questions [2] => Strings [3] => No-of-triangles- )
Given an array of integers. Find the number of triangles can form using the any 3 elements as a sides of triangle. One element in array should be used only once.
First line contains the size of the first array. Next line contains the m integers separated by the spaces.
Print the number of triangles can form.
4 3 1 6 4
1
6 7 3 1 1 7 6
5
5 8 2 11 4 15
0
Login to see Discussion
Approach1: Triangle Inequality
Step-i) Initialize variables I,j,k with 3 for loops.
Step-ii) in first 2 for loops adding elements of a[i] and a[j].
Step-iii) comparing if the sum is greater than a[k] or not and counting all possible cases.
Step-iv) Finally return the possible count.
Time Complexity: O(n^3)
Space Complexity: O(n)
Approach2:
Step-i) Sort the array first.
Step-ii) Take the first element as i and last element as j.
Step-iii) Now to pick the third element we will find based on the sum.
Step-iv) Based on the sum we have move the i and j.
Step-v) if sum is less than the element fixed we increase i value else decrease the j value.
Step-vi) We can keep a track count and return count.
Time Complexity: O(n logn)
Space Complexity: O(n)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution