Zero Pair Sum

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
32 upvotes
Asked in companies
Urban Company (UrbanClap)DunzoNickelfox Technologies

Problem statement

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

 

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
1 -1 2 -2
5
1 2 3 4 5
Sample Output 1 :
2
0
Explanation Of Sample Output 1 :
For test case 1 :
Two pairs exist which have their sums equal to zero:
Pair formed by the first two elements has sum equal to zero, ie: 1 + (-1) = 0
Also, the pair formed by the last two elements has a sum equal to zero, ie: 2 + (-2) = 0 

For test case 2 :
No pair can be formed with a sum equal to zero.
Sample Input 2 :
2
3
10 -5 -5
1
5
Sample Output 2 :
0
0
Hint

Try evaluating each possible pair.

Approaches (2)
Brute Force

 

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 :

  1. Initialize count to 0.
  2. Run outer for loop for x from 0 to N-2
  3. Run inner for loop for y from x+1 to N-1
  4. For each generated pair of (x,y) increment the count if the arr[x]+arr[y] =0
  5. Return the final value of count.
Time Complexity

O( N^2 ), where N is the size of the input array.


Since we evaluate all N*(N-1)/2 possible pairs, Hence the time complexity is O(N^2) 

Space Complexity

O ( 1 )

 

Since constant space is used. Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Zero Pair Sum
Full screen
Console