Last Updated: 29 Jul, 2020
Count Positive - Negative Pairs
Easy
Asked in companies
You have been given an array/list(ARR) of positive and negative integers. Print the number of pairs where:
arr[i] = -arr[j] and i != j
Note:
Given array/list can contain duplicate elements and will not contain '0'.
(arr[i],arr[j]) and (arr[j],arr[i]) are considered same.
Input format :
The first line of each test case contains an integers 'N' where 'N' denotes the size of array/list(ARR).
The next line contains 'N' space-separated integers representing array elements.
Output format :
Print the total number of positive-negative pairs present in the array/list.
Note:
You are not required to print the output explicitly, it has already been taken care of. Just implement the function.
Constraints :
1 <= N <= 10^5
-10^9 <= arr[i] <= 10^9
Time Limit: 1 sec
Approaches
- Initialize the totalPairs = 0.
- Run two loops first from i = 0 to n-1 and second from j = i+1 to n-1 and if arr[i] == -arr[j] then increase the totalPairs by 1.
- Return totalPairs.
We can observe that the sum of the two elements is 0 when they make a positive-negative pair.
- Sort the array and take two pointers i and j, one pointer pointing to the start of the array i.e. i = 0, and another pointer pointing to the end of the array i.e. j = n – 1. If arr[i] + arr[j]
- Is greater than the 0 then decrements j.
- Lesser than the 0 then increments i.
- Equals the 0 then count such pairs.
- To count the pairs when arr[i] + arr[j] = 0
- Count number of elements equal to the arr[i]
- Count number of elements equal to the arr[j]
- Then totalPairs will be increased by the product of the count of elements equal to arr[i] and the count of elements equal to arr[j].
- Create a hashmap/dictionary which will store the count of occurrences of each element and initially it will be empty.
- Run a loop from i=0 to N-1 and for each i’th element its value is arr[i] and we need to find the number which is equal to - arr[i]. So check if -arr[i] is present in the hashmap/dictionary if it is present, the answer will be increased by the count of occurrence of -arr[i] present in the hashmap/dictionary as arr[i] can be paired with all those elements equal to -arr[i] present in its left side.
- Now increase the count of arr[i] in the hashmap/dictionary by 1.