Given an array of integers, we need to find out all possible ways construct non-degenerate triangle using array values as its sides. If no such triangle can be formed then return 0.
 
Example 1:
Input : [5, 4, 3, 1, 2]
Output : 3
Explanation:
Sides of possible triangle are
(2 3 4), (3 4 5) and (2 4 5)
 
Example 2:
Input : [4, 1, 2]
Output : 0 
No triangle is possible from given
array values
Your Task:  
You don't need to read input or print anything. Your task is to complete the function noOfTriangles() which takes the vector v[] and its size N as inputs and returns the count of all possible triangles that can be formed using the values from the array.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{3}
1 ≤ A[i] ≤ 10^{4}

Difficulty: EASY
Tags: Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
    def noOfTriangles( self, arr, n):
    # Your code goes here







    


Solutions:
class Solution:

	def noOfTriangles(self, arr, n):
		arr.sort()
		ans = 0
		for i in range(n - 1, 1, -1):
			x = 0
			y = i - 1
			while x < y:
				if arr[x] + arr[y] > arr[i]:
					ans += y - x
					y -= 1
				else:
					x += 1
		return ans


class Solution:

	def noOfTriangles(self, arr, n):
		arr = sorted(arr)
		count = 0
		for i in range(len(arr) - 1, 1, -1):
			l = 0
			r = i - 1
			while l < r:
				if arr[l] + arr[r] > arr[i]:
					count += r - l
					r -= 1
				else:
					l += 1
		return count


class Solution:

	def noOfTriangles(self, arr, n):
		temp = sorted(arr)
		count = 0
		for i in range(n - 1, 1, -1):
			low = 0
			high = i - 1
			while low < high:
				if temp[low] + temp[high] > temp[i]:
					count += high - low
					high -= 1
				else:
					low += 1
		return count


class Solution:

	def noOfTriangles(self, arr, n):
		arr.sort()
		count = 0
		i = n - 1
		while i >= 2:
			start = 0
			end = i - 1
			while start < end:
				if arr[start] + arr[end] > arr[i]:
					count += end - start
					end -= 1
				else:
					start += 1
			i -= 1
		return count


class Solution:

	def noOfTriangles(self, arr, n):
		arr.sort()
		count = 0
		for i in range(len(arr) - 1, 1, -1):
			left = 0
			right = i - 1
			while left < right:
				sum = arr[left] + arr[right]
				if sum > arr[i]:
					count += right - left
					right -= 1
				else:
					left += 1
		return count


class Solution:

	def noOfTriangles(self, arr, N):
		arr.sort()
		c = 0
		for i in range(N - 1, -1, -1):
			l = 0
			r = i - 1
			while l < r:
				if arr[l] + arr[r] > arr[i]:
					c += r - l
					r -= 1
				else:
					l += 1
		return c


class Solution:

	def noOfTriangles(self, arr, n):
		arr.sort()
		j = n - 1
		ans = 0
		while j > 1:
			(start, end) = (0, j - 1)
			while start < end:
				if arr[start] + arr[end] <= arr[j]:
					start += 1
				else:
					ans += end - start
					end -= 1
			j -= 1
		return ans


class Solution:

	def noOfTriangles(self, arr, n):
		count = 0
		if n < 3:
			return 0
		arr.sort()
		for c in range(n - 1, 1, -1):
			b = c - 1
			a = 0
			while a != b:
				if arr[a] + arr[b] > arr[c]:
					count += b - a
					b -= 1
				else:
					a += 1
		return count

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.noOfTriangles(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def noOfTriangles(self, arr, n):
		count = 0
		arr.sort()
		for i in range(n - 2):
			k = i + 2
			for j in range(i + 1, n - 1):
				if arr[i] != 0:
					while k < n and arr[i] + arr[j] > arr[k]:
						k = k + 1
					count += k - j - 1
		return count

def main():
	T = int(input())
	while T > 0:
		n = int(input())
		a = [int(x) for x in input().strip().split()]
		ob = Solution()
		print(ob.noOfTriangles(a, n))
		T -= 1
if __name__ == '__main__':
	main()


class Solution:

	def noOfTriangles(self, arr, n):
		count = 0
		arr.sort()
		i = n - 1
		while i >= 2:
			s = 0
			e = i - 1
			while s < e:
				if arr[s] + arr[e] > arr[i]:
					count += e - s
					e -= 1
				else:
					s += 1
			i -= 1
		return count


class Solution:

	def noOfTriangles(self, arr, n):
		arr.sort()
		c = 0
		for i in range(n - 1, 1, -1):
			l = 0
			h = i - 1
			while l < h:
				if arr[l] + arr[h] > arr[i]:
					c += h - l
					h -= 1
				else:
					l += 1
		return c


class Solution:

	def noOfTriangles(self, arr, n):
		cnt = 0
		arr.sort(reverse=True)
		if n < 3:
			return 0
		for i in range(n - 2):
			s = i + 1
			e = n - 1
			while s < e:
				sm = arr[s] + arr[e]
				if sm > arr[i]:
					cnt += e - s
					s += 1
				else:
					e -= 1
		return cnt