DAY 7 OF GEEKS FOR GEEKS 30DAYSOFCODE

Valid Pair Sum (Level- Medium)

Given an array of size N, find the number of distinct pairs {a[i], a[j]} (i != j) in the array with their sum greater than 0.

Example-1:

Input: N = 3, a[] = {3, -2, 1}
Output: 2
Explanation: {3, -2}, {3, 1} are two 
possible pairs.

Expected Time Complexity: O(N * Log(N))
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 10⁵
-104 ≤ a[i] ≤ 10⁴

Solution Code:

class Solution
{
static long ValidPair(int arr[], int n)
{
Arrays.sort(arr);

// Variable to store the count of pairs
long ans = 0;

// Loop to iterate through the array
for (int i = 0; i < n; ++i) {

// Ignore if the value is negative
if (arr[i] <= 0)
continue;

/*
minReqVal val is the min value ,which will
give >=1 after adding with the arr[i]
*/
int minReqVal = -arr[i] + 1;
int j = lower_bound(arr, minReqVal);

if (j >= 0)
ans += i — j;
}
return ans;
}

/*
it return the index of a minimum Number in the
array which is just >= val
*/
static int lower_bound(int arr[], int val)
{
int start = 0, end = arr.length;

/*
using the Binary search technique , since our
array is sorted
*/
while (start < end) {
int mid = (start + end) >> 1;

if (val > arr[mid])
start = mid + 1;
else
end = mid;
}

// when we dont find the answer return -1
if (start == arr.length)
return -1;

return start;
}


}