Given an array of size N, find the number of distinct pairs {i, j} (i != j) in the array such that the sum of a[i] and a[j] is greater than 0.
Example 1:
Input: N = 3, a[] = {3, -2, 1}
Output: 2
Explanation: {3, -2}, {3, 1} are two 
possible pairs.
Example 2:
Input: N = 4, a[] = {-1, -1, -1, 0}
Output: 0
Explanation: There are no possible pairs.
Your Task:  
You don't need to read input or print anything. Complete the function ValidPair() which takes the array a[ ] and size of array N as input parameters and returns the count of such pairs.
Expected Time Complexity: O(N * Log(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{5} 
-10^{4}  ≤ a[i] ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Sorting

Data structures

Greedy algorithms

Starter code: #User function Template for python3

class Solution:
    def ValidPair(self, a, n): 
    	# Your code goes here

Solutions:
class Solution:

	def ValidPair(self, a, n):
		a.sort()
		count = 0
		i = 0
		j = n - 1
		while i < j:
			if a[i] + a[j] > 0:
				count += j - i
				j -= 1
			else:
				i += 1
		return count


class Solution:

	def ValidPair(self, a, n):
		a.sort()
		(left, right) = (0, n - 1)
		count = 0
		while left < right:
			data = a[left] + a[right]
			if data > 0:
				count += right - left
				right -= 1
			else:
				left += 1
		return count


from bisect import bisect_left as lower_bound

class Solution:

	def ValidPair(self, a, n):
		distinctPair = 0
		a.sort()
		i = n - 1
		while i > 0:
			if a[i] <= 0:
				break
			else:
				j = lower_bound(a, -a[i] + 1)
				distinctPair = distinctPair + (i - j)
				i = i - 1
		return distinctPair


class Solution:

	def ValidPair(self, a, n):
		a.sort()
		i = 0
		while a[i] < 0:
			i += 1
		j = i
		t = n - j
		i -= 1
		ans = 0
		while i >= 0 and j < n:
			if a[i] + a[j] < 0:
				j += 1
			elif a[i] + a[j] > 0:
				i -= 1
				ans += n - j
			else:
				j += 1
		ans += t * (t - 1) // 2
		return ans


import bisect

class Solution:

	def ValidPair(self, a, n):
		a.sort()
		ans = 0
		for i in range(n):
			if a[i] < 0:
				ans += n - bisect.bisect(a, -a[i])
			else:
				ans += n - (i + 1)
		return ans


class Solution:

	def ValidPair(self, a, n):
		a.sort()
		for i in range(n):
			if a[i] >= 0:
				break
		pos = n - i - 1
		j = i
		i = i - 1
		ans = 0
		cnt = 0
		while j < n and i >= 0:
			while i >= 0 and a[i] + a[j] > 0:
				i -= 1
				cnt += 1
			ans += pos + cnt
			pos -= 1
			j += 1
		while i < 0 and j < n:
			ans += pos + cnt
			pos -= 1
			j += 1
		return ans


class Solution:

	def ValidPair(self, a, n):
		a.sort()
		start = 0
		end = n - 1
		cnt = 0
		while start < end:
			if a[end] + a[start] > 0:
				cnt += end - start
				end -= 1
			else:
				start += 1
		return cnt


from bisect import bisect_left

class Solution:

	def ValidPair(self, a, n):
		a.sort()
		count = 0
		for i in range(n):
			if a[i] <= 0:
				continue
			j = bisect_left(a, 1 - a[i])
			count += i - j
		return count


class Solution:

	def ValidPair(self, a, n):
		a.sort()
		count = 0
		j = n - 1
		for i in range(n):
			while j > i and a[i] + a[j] > 0:
				j -= 1
			if j == i:
				count += (n - 1 - i) * (n - i) // 2
				break
			count += n - j - 1
		return count


class Solution:

	def ValidPair(self, a, n):
		a.sort()
		count = 0
		l = 0
		r = n - 1
		while l < r:
			if a[l] + a[r] > 0:
				count += r - l
				r -= 1
			else:
				l += 1
		return count


class Solution:

	def ValidPair(self, arr, n):
		arr.sort()
		count = 0
		(i, j) = (0, n - 1)
		while i < j:
			if arr[i] + arr[j] > 0:
				j -= 1
			else:
				count += n - j - 1
				i += 1
		pos = n - j - 1
		count += pos * (pos + 1) // 2
		return count


import math

class Solution:

	def ValidPair(self, a, N):
		a.sort()
		count = 0
		Nofpostive = 0
		Nofnegative = 0
		for i in range(N):
			if a[i] >= 0:
				Nofpostive += 1
			else:
				Nofnegative += 1
		if Nofpostive >= 2:
			count = math.factorial(Nofpostive) / (math.factorial(Nofpostive - 2) * 2)
		fpos = -1
		for i in range(N):
			if a[i] > 0:
				fpos = i
				break
		j = fpos
		i = fpos - 1
		if a[i] == 0:
			i -= 1
			Nofpostive -= 1
		while j < N and i >= 0:
			if a[j] > abs(a[i]):
				count += Nofpostive
				i -= 1
			else:
				Nofpostive -= 1
				j += 1
		return int(count)


from bisect import bisect_right as ub

class Solution:

	def ValidPair(self, a, n):
		a.sort()
		c = 0
		for i in range(n):
			if a[i] >= 0:
				cei = n - i - 1
			else:
				l = ub(a, -a[i])
				cei = n - l
			c += cei
		return c


from bisect import bisect_left as lower_bound

class Solution:

	def ValidPair(self, a, n):
		a = sorted(a)
		ans = 0
		for i in range(n):
			if a[i] <= 0:
				continue
			j = lower_bound(a, -a[i] + 1)
			ans += i - j
		return ans


class Solution:

	def ValidPair(self, a, n):
		count = 0
		a.sort()
		low = 0
		high = n - 1
		while low < high:
			if a[low] + a[high] > 0:
				count += high - low
				high -= 1
			else:
				low += 1
		return count


class Solution:

	def ValidPair(self, a, n):
		a = sorted(a)
		for i in range(n):
			if a[i] > 0:
				break
		e = i
		s = i - 1
		su = 0
		m = []
		while e < n:
			if s >= 0 and a[s] + a[e] > 0:
				s = s - 1
			else:
				su = su + e - s - 1
				e = e + 1
		return su


class Solution:

	def ValidPair(self, arr, n):
		ans = 0
		arr.sort()
		(l, r) = (0, n - 1)
		while l < r:
			if arr[l] + arr[r] > 0:
				ans += r - l
				r -= 1
			else:
				l += 1
		return ans


class Solution:

	def ValidPair(self, A, N):
		A.sort()
		(i, j) = (0, N - 1)
		ans = 0
		while i < j:
			if A[i] + A[j] > 0:
				j -= 1
			else:
				ans += N - j - 1
				i += 1
		L = N - j - 1
		ans += L * (L + 1) // 2
		return ans


class Solution:

	def ValidPair(self, a, n):
		c = 0
		a.sort()
		i = 0
		k = n - 1
		while i < k:
			if a[i] + a[k] > 0:
				c += k - i
				k -= 1
			else:
				i += 1
		return c


class Solution:

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


class Solution:

	def ValidPair(self, a, n):
		a.sort()
		count = 0
		i = 0
		j = n - 1
		while i < j:
			while i < j and a[i] + a[j] <= 0:
				i += 1
			if i != j:
				count += j - i
			j -= 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		array = list(map(int, input().strip().split()))
		obj = Solution()
		ans = obj.ValidPair(array, n)
		print(ans)


import bisect

class Solution:

	def ValidPair(self, a, n):
		a.sort()
		ans = 0
		for i in range(n - 1):
			if a[i] > 0:
				k = n - i - 1
				ans += k * (k + 1) // 2
				return ans
			ind = bisect.bisect_left(a, 1 - a[i])
			if ind < n:
				ans += n - ind
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		array = list(map(int, input().strip().split()))
		obj = Solution()
		ans = obj.ValidPair(array, n)
		print(ans)


class Solution:

	def ValidPair(self, a, n):
		a.sort()
		count = 0
		l = 0
		r = n - 1
		while l < r:
			temp = a[l] + a[r]
			if temp > 0:
				count += r - l
				r -= 1
			else:
				l += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		array = list(map(int, input().strip().split()))
		obj = Solution()
		ans = obj.ValidPair(array, n)
		print(ans)


class Solution:

	def ValidPair(self, a, n):
		a.sort(reverse=True)
		(low, high) = (0, n - 1)
		count = 0
		while low <= high:
			msum = a[low] + a[high]
			if msum <= 0:
				high -= 1
			else:
				count += high - low
				low += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		array = list(map(int, input().strip().split()))
		obj = Solution()
		ans = obj.ValidPair(array, n)
		print(ans)


class Solution:

	def ValidPair(self, a, n):
		ans = 0
		(front, tail) = (0, n - 1)
		a.sort()
		while front < tail:
			if a[front] + a[tail] > 0:
				ans += tail - front
				tail -= 1
			else:
				front += 1
		return ans


class Solution:

	def ValidPair(self, a, n):
		a.sort()
		left = 0
		rigth = n - 1
		count = 0
		while left < rigth:
			if a[left] + a[rigth] > 0:
				count = count + (rigth - left)
				rigth = rigth - 1
			else:
				left = left + 1
		return count


class Solution:

	def upper_bound(self, a, l, r, k):
		pos = r + 1
		while l <= r:
			mid = (l + r) // 2
			if a[mid] > k:
				pos = mid
				r = mid - 1
			else:
				l = mid + 1
		return pos

	def ValidPair(self, a, n):
		ans = 0
		a.sort()
		positive = 0
		for i in range(0, n):
			if a[i] > 0:
				positive = n - i
				break
			else:
				pos = self.upper_bound(a, i, n - 1, abs(a[i]))
				ans = ans + n - pos
		ans = ans + positive * (positive - 1) // 2
		return ans


class Solution:

	def ValidPair(self, a, n):
		import bisect
		a.sort()
		if a[-1] <= 0:
			return 0
		if a[0] > 0:
			return n * (n - 1) // 2

		def helper(i):
			j = bisect.bisect_left(a, -a[i] + 1, i + 1, n)
			if j == n:
				return -1
			else:
				return j
		ans = 0
		for i in range(n - 1):
			if a[i] > 0:
				ans += n - i - 1
				continue
			j = helper(i)
			if j != -1:
				ans += n - j
		return ans


class Solution:

	def ValidPair(self, a, n):
		a.sort(reverse=True)
		res = 0
		l = 0
		h = n - 1
		while l <= h:
			m = a[l] + a[h]
			if m <= 0:
				h -= 1
			else:
				res += h - l
				l += 1
		return res


class Solution:

	def ValidPair(self, a, n):
		a = sorted(a)
		i = 0
		j = n - 1
		c = 0
		u = []
		while i < j:
			if a[i] + a[j] > 0:
				c += j - i
				j = j - 1
			else:
				i += 1
		return c


class Solution:

	def ValidPair(self, a, n):
		negative = []
		positive = []
		for num in a:
			if num >= 0:
				positive.append(num)
			else:
				negative.append(num)
		positive = sorted(positive, reverse=True)
		negative = sorted(negative)
		pairs = 0
		posNum = 0
		for negNum in negative:
			while posNum < len(positive) and negNum + positive[posNum] > 0:
				posNum += 1
			pairs = pairs + posNum
		numberOfPositives = len(positive)
		pairs += numberOfPositives * (numberOfPositives - 1) // 2
		return pairs


class Solution:

	def ValidPair(self, a, n):
		ans = 0
		a.sort()
		mod = 10 ** 9 + 7
		i = 0
		j = len(a) - 1
		while i < j:
			if a[i] + a[j] > 0:
				ans += (j - i) % mod
				j -= 1
			else:
				i += 1
		return ans


class Solution:

	def ValidPair(self, a, n):
		a.sort(reverse=True)
		i = 0
		j = n - 1
		c = 0
		s = 0
		while i <= j:
			s = a[i] + a[j]
			if s <= 0:
				j -= 1
			else:
				c += j - i
				i += 1
		return c


from bisect import bisect_left as bl

class Solution:

	def ValidPair(self, a, n):

		def binSearch(a, x, i):
			l = i
			r = len(a) - 1
			while l < r:
				mid = (l + r) // 2
				if a[mid] + x <= 0:
					l = mid + 1
				else:
					r = mid
			return l if a[l] + x > 0 else -1
		a.sort()
		pairs = 0
		for i in range(n - 1):
			target = max(bl(a, 1 - a[i]), i + 1)
			pairs += n - target
		return pairs


class Solution:

	def ValidPair(self, a, n):
		cnt = 0
		d = {}
		a.sort()
		i = 0
		j = n - 1
		while i < j:
			if a[i] + a[j] > 0:
				cnt += j - i
				j -= 1
			else:
				i += 1
		return cnt


class Solution:

	def ValidPair(self, a, n):
		t = 0
		a.sort(reverse=True)
		low = 0
		high = n - 1
		while low <= high:
			s = a[low] + a[high]
			if s <= 0:
				high -= 1
			else:
				t += high - low
				low += 1
		return t


class Solution:

	def ValidPair(self, a, n):
		a = sorted(a)
		(l, h) = (0, n - 1)
		c = 0
		while l < h:
			m = a[l] + a[h]
			if m <= 0:
				l += 1
			else:
				c += h - l
				h -= 1
		return c


class Solution:

	def ValidPair(self, a, n):
		a.sort(reverse=True)
		(l, r) = (0, n - 1)
		cnt = 0
		while l <= r:
			temp = a[l] + a[r]
			if temp <= 0:
				r -= 1
			else:
				cnt += r - l
				l += 1
		return cnt


class Solution:

	def ValidPair(self, arr, n):
		arr.sort()
		ans = 0
		low = 0
		high = n - 1
		while low < high:
			if arr[low] + arr[high] > 0:
				ans += high - low
				high -= 1
			else:
				low += 1
		return ans


class Solution:

	def ValidPair(self, a, n):
		c = 0
		a.sort()
		i = 0
		j = n - 1
		while i < j:
			if a[i] + a[j] >= 1:
				c += j - i
				j -= 1
			elif a[i] <= 1:
				i += 1
		return c


class Solution:

	def ValidPair(self, a, n):
		a.sort()
		l = 0
		h = n - 1
		c = 0
		while l < h:
			if a[l] + a[h] > 0:
				c += h - l
				h -= 1
			else:
				l += 1
		return c


class Solution:

	def ValidPair(self, a, n):
		arr = a
		a.sort()
		p_index = -1
		for i in range(n - 1, -1, -1):
			if a[i] > 0:
				p_index = i
			else:
				break
		if p_index == -1:
			return 0
		num = n - p_index
		count = num * (num - 1) // 2
		for j in range(p_index - 1, -1, -1):
			while p_index < n and arr[j] + arr[p_index] <= 0:
				p_index += 1
			if p_index > n - 1:
				break
			count += n - p_index
		return count


class Solution:

	def ValidPair(self, arr, n):
		arr.sort()
		(left, right) = (0, n - 1)
		count = 0
		while left <= right:
			if arr[left] + arr[right] <= 0:
				left += 1
			else:
				count += right - left
				right -= 1
		return count


class Solution:

	def ValidPair(self, a, n):
		a.sort()
		i = 0
		j = n - 1
		ans = 0
		while i <= j:
			s = a[i] + a[j]
			if s <= 0:
				i = i + 1
			else:
				ans = ans + (j - i)
				j = j - 1
		return ans


class Solution:

	def ValidPair(self, a, n):
		cnt = 0
		low = 0
		high = n - 1
		a.sort()
		while low < high:
			_sum = a[low] + a[high]
			if _sum <= 0:
				low += 1
			elif _sum > 0:
				cnt += high - low
				high -= 1
		return cnt