New update is available. Click here to update.

Count Positive - Negative Pairs

PROBLEM STATEMENT

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

Approach 1

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.

Try Problem

Approach 2

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].

Try Problem

Approach 3

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.

Try Problem

Count Positive - Negative Pairs

PROBLEM STATEMENT

You have been given an array/list(ARR) of positive and negative integers. Print the number of pairs where:

Note:

Input format :

Output format :

Note:

Constraints :

Approach 1

Approach 2

Approach 3

Interested in Coding Ninjas Flagship Courses?