PYTHON

Find number of triangles that can be made by given sides of triangle

"""The time complexity can be greatly reduced using Two Pointer methods in just two nested loops.
Approach: First sort the array, and run a nested loop, fix an index and then try to fix an upper and lower index within which we can use all the lengths to form a triangle with that fixed index.
Algorithm:
Sort the array and then take three variables l, r and i, pointing to start, end-1 and array element starting from end of the array.
Traverse the array from end (n-1 to 1), and for each iteration keep the value of l = 0 and r = i-1
Now if a triangle can be formed using arr[l] and arr[r] then triangles can obviously formed 
from a[l+1], a[l+2]…..a[r-1], arr[r] and a[i], because the array is sorted , which can be directly calculated using (r-l). and then decrement the value of r and continue the loop till l is less than r
If a triangle cannot be formed using arr[l] and arr[r] then increment the value of l and continue the loop till l is less than r 
So the overall complexity of iterating 
through all array elements reduces.
"""
# Python implementation of the above approach
def CountTriangles( A):
 
    n = len(A);
 
    A.sort();
 
    count = 0;
     
    for i in range(n - 1, 0, -1):
        l = 0;
        r = i - 1;
        while(l < r):
            if(A[l] + A[r] > A[i]):
 
                # If it is possible with a[l], a[r]
                # and a[i] then it is also possible
                # with a[l + 1]..a[r-1], a[r] and a[i]
                count += r - l;
 
                # checking for more possible solutions
                r -= 1;
             
            else:
 
                # if not possible check for
                # higher values of arr[l]
                l += 1;
    print("No of possible solutions: ", count);
 
# Driver Code
if __name__ == '__main__':
 
    A = [ 4, 3, 5, 7, 6 ];
 
    CountTriangles(A);
     
# This code is contributed by PrinciRaj1992