Home > Backend Development > C++ > Find the number of unique pairs in an array using C++

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

WBOY
Release: 2023-09-07 11:53:09
forward
554 people have browsed it

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
Copy after login

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;
}
Copy after login

Output

Number of unique pairs : 16
Copy after login
Copy after login

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;
}
Copy after login

Output

Number of unique pairs : 16
Copy after login
Copy after login

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!

Related labels:
source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template