Last Updated: 22 Jul, 2021
Zero Pair Sum
Moderate
Asked in companies
You are given an array ‘arr’ of ‘N’ integers. Your task is to find the count of pairs with a sum equal to zero.
Specifically, find the count of all pairs ( i , j ) such that i < j and arr[i] + arr[j] = 0
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows
The first line of each test case contains a single integers ‘N’ denoting the length of the array.
The second line of each test case contains ‘N’ integers denoting the array elements.
Output Format :
For each test case print a single integer denoting the count of pairs with zero-sum.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 10^4
10^-9 <= arr[i] <= 10^9
Time limit: 1 sec
Approaches
We can generate all pairs possible and check whether their sum is equal to zero.
To generate all the pairs: for each x in the range [0, N-2] iterate through all y in the range [x+1, N-1].
The steps are as follows :
- Initialize count to 0.
- Run outer for loop for x from 0 to N-2
- Run inner for loop for y from x+1 to N-1
- For each generated pair of (x,y) increment the count if the arr[x]+arr[y] =0
- Return the final value of count.
Create a hash-map to store the count of the frequency of each array element. Now simply iterate on the created hash-map, if the current key is equal to x then search if -x exists in the hash-map or not, if it exists then add the frequency of x multiplied by the frequency of -x to the count. Notice that we are double counting things here, so remember to return count/2.
Remember to separately handle the border case when array element is equal to 0.
The steps are as follows :
- Initialize count to 0.
- Create a hash-map to store the frequency of each array element.
- Iterate the hash-map, if the current key is equal to curKey and (curKey !=0), search if -curKey exists.
- Multiply frequency of curKey and frequency of -curKey, and add it to count
- If the frequency of elements equal to 0 is f, add f * (f-1) to count
- Return the final value of count / 2