Find the number of unique pairs in an array using C++

We need proper knowledge to create several unique pairs in C's array syntax. While finding the number of unique pairs, we count all the unique pairs in the given array i.e. all possible pairs can be formed where each pair should be unique. For example-

Input : array[ ] = { 5, 5, 9 }
Output : 4
Explanation : The number of all unique pairs are (5, 5), (5, 9), (9, 5) and (9, 9).

Input : array[ ] = { 5, 4, 3, 2, 2 }
Output : 16

Methods to find solution

There are two ways to solve this problem, they are −

brute force method

In this method , we will loop through each possible pairing, add these pairs to a set, and finally find the size of the set. The time complexity of this method is O(n2 log n).

Example

#include <bits/stdc++.h>
using namespace std;
int main () {
   int arr[] = { 5, 4, 3, 2, 2 };
   int n = sizeof (arr) / sizeof (arr[0]);
   // declaring set to store pairs.
   set < pair < int, int >>set_of_pairs;

   for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
         set_of_pairs.insert (make_pair (arr[i], arr[j]));

   int result = set_of_pairs.size();

   cout <<"Number of unique pairs : " << result;
   return 0;
}

Output

Number of unique pairs : 16

Explanation of the above code

In this code, first we declare a collection variable and then use two Loop through every possible pair of elements and insert each pair into the set using i and j. Then we calculate the size of the collection and print the result.

Efficient method

Another way is to first find out the number of unique numbers in the array; now every other unique element can be created with any other unique element except itself one pair, so the number of unique pairs is equal to the square of all unique numbers. The time complexity of this method is O(n).

Example

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

int main () {
   int arr[] = { 5, 4, 3, 2, 2 };
   int n = sizeof (arr) / sizeof (arr[0]);

   // declaring set to store unique elements.

   unordered_set < int >set_of_elements;
   // inserting elements in the set.
   for (int i = 0; i < n; i++)
      set_of_elements.insert (arr[i]);

   int size = set_of_elements.size ();
   // finding number of unique pairs
   int result = size * size;

   cout << "Number of unique pairs in an array: " << result;
   return 0;
}

Output

Number of unique pairs : 16

Explanation of the above code

In this code, we declare a collection and then iterate through each element of the array elements, inserting each element into the collection. After that, we calculated the size of the set and found the result according to the formula n2 and printed the output.

Conclusion

In this article, we solved the problem of finding unique pairs in an array and discussed two solutions, namely simple and efficient. In the simple approach we insert all possible pairs into the set with O(n2 log n) time complexity, while in the efficient approach we find all unique numbers and find the result by n2. We can write the same program in other languages ​​like C, Java, Python and others. Hope you find this article helpful.

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