Last Updated: 18 Dec, 2020
Positive Negative Pair
Easy
Asked in companies
Given an array of distinct integers, find all the pairs having positive value and negative value of a number that exists in the array. Return the pairs in any order.
Note:
The pair consists of equal absolute values, one being positive and another negative.
Return an empty array, if no such pair exists.
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2T’ lines represent the ‘T’ test cases.
The first line of each test case contains an integer ‘N’ denoting the number of integers in the array.
The second line of each test case contains ‘N’ space-separated integers which denote the elements of the array.
Output Format:
For each test case, print all pairs with equal absolute value with one being positive and another negative.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
-10^5 <= A[i] <= 10^5
Time Limit: 1 second
Approaches
- We use two nested loops to find the solution.
- We make a vector to store positive and negative pairs.
- For each element arr[i], find the corresponding negative of arr[i] from index ‘i + 1’ to ‘n – 1’ and store it in another array.
- Return the answer vector.
The idea is to use binary search.
- Sort the Array.
- Iterate the array, if there is any positive integer to find whether the negative pair for that number is available or not using binary search.
- If there is a negative-positive pair available then add it to the answer pair vector.
- Return the vector.
- The idea is to use hashing. Make a boolean array, 'VISITED’ of 10^5+2, and initialize it to false.
- Traverse the given array, make the bool true at the absolute value of positive integers in the boolean array.
- We make a vector to store every positive integer which has its negative pair.
- Traverse the given array, check whether the absolute value of negative integers has a true boolean value or not. If they do then store the absolute value in the vector.
- Make a new vector and store every value of the above vector with their negative pair together.