Find pairs of positive and negative values ​​in an array using C++

In this article, we have an array containing different elements. We need to print the pairs of positive and negative values ​​in the array with the same absolute value and print them in sorted order like -

Input : arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88}
Output : -1 1 -12 12 -56 56

Input : arr[] = {30, 40, 50, 77, -51, -50, -40}
Output : -40 40 -50 50

Methods to find the solution

The first method we thought of was brute force method, and then we also came up with a method called the high-efficiency method. We will discuss both methods.

Brute force method

In this method, we will traverse the array with one index and find the same absolute value but different index.

Example

#include<bits/stdc++.h>
using namespace std;

int main() {
   int arr[] = { 1, -1, 11, 12, 56, 77, -56, -12, -88 };
   int n = sizeof(arr)/sizeof(int); // size of our array.
   vector<int> nums; // the present pairs.

   for(int i = 0; i < n; i++) {
      for(int j = i+1; j < n; j++) {
         if(abs(arr[j]) == abs(arr[i])) { // finding the pairs.
            nums.push_back(abs(arr[i]));
            break;
            // if we found the pair then we can just break as there are distinct elements in the array.
         }
      }
   }
   sort(nums.begin(), nums.end());
   for(auto x : nums) // printing the pairs.
      cout << -x << " " << x << " ";
}

Output

-1 1 -12 12 -56 56

In this method, we use two loops to traverse the array and find another element; if we find another element, we Will jump out of the inner loop to speed up the code. Now we use two for loops, and the overall time complexity is O(N*N). N is the size of the given array, works fine for lower constraints, but not good for higher constraints, so now we will discuss another approach.

Efficient method

In this method, we will use a hash map, which will greatly reduce our time complexity.

Example

#include<bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = { 4, 8, 9, -4, 1, -1, -8, -9 };
   int n = sizeof(arr)/sizeof(int); // size of our array.
   map<int, int> found; // going to store the count of numbers found.
   vector<int> nums; // the present pairs.
   for(int i = 0; i < n; i++)
      found[abs(arr[i])]++; // increasing the frequency of abs(arr[i]).
   for(auto x : found) { // traversing the map.
      if(x.second == 2) // if any numbers frequency is two then push it to nums.
         nums.push_back(x.first);
   }
   for(auto x : nums) // printing the pairs.
      cout << -x << " " << x << " ";
}

Output

-1 1 -4 4 -8 8 -9 9

Explanation of the above code

In this method, we use a hash map to store the frequency of numbers; when As we iterate over the array, we are now updating the frequency of the absolute value of the current element because you know that all pairs have a value of 2, so we are iterating over the map.

If the frequency of any number is 2, then we store it in nums and finally, we print the values ​​in sorted order. (Since the map contains numbers in sorted order, we don't need to sort the numeric vectors).

Conclusion

In this article, we solved the problem of finding pairs of positive and negative values ​​in an array using hashing techniques. We also learned a C program to solve this problem and a complete way to solve this problem (normal and efficient). We can write the same program in other languages ​​such as C, java, python and other languages. We hope this article was helpful to you.

The above is the detailed content of Find pairs of positive and negative values ​​in an array using C++. For more information, please follow other related articles on the PHP Chinese website!