Dado un arreglo de N elementos, la tarea es encontrar todos los pares únicos que se pueden formar usando los elementos de un arreglo dado.
Ejemplos:
Entrada: arr[] = {1, 1, 2}
Salida: 4
(1, 1), (1, 2), (2, 1), (2, 2) son los únicos pares posibles.Entrada: arr[] = {1, 2, 3}
Salida: 9
Enfoque ingenuo: la solución simple es iterar a través de todos los pares posibles y agregarlos a un conjunto y luego averiguar el tamaño del conjunto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number
// of unique pairs in the array
int countUnique(int arr[], int n)
{
// Set to store unique pairs
set<pair<int, int> > s;
// Make all possible pairs
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
s.insert(make_pair(arr[i], arr[j]));
// Return the size of the set
return s.size();
}
// Driver code
int main()
{
int arr[] = { 1, 2, 2, 4, 2, 5, 3, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countUnique(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.awt.Point;
import java.util.*;
class GFG
{
// Function to return the number
// of unique pairs in the array
static int countUnique(int arr[], int n)
{
// Set to store unique pairs
Set<Point> s = new HashSet<>();
// Make all possible pairs
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
s.add(new Point(arr[i], arr[j]));
// Return the size of the set
return s.size();
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 2, 4, 2, 5, 3, 5 };
int n = arr.length;
System.out.print(countUnique(arr, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # Function to return the number # of unique pairs in the array def countUnique(arr, n): # Set to store unique pairs s = set() # Make all possible pairs for i in range(n): for j in range(n): s.add((arr[i], arr[j])) # Return the size of the set return len(s) # Driver code arr = [ 1, 2, 2, 4, 2, 5, 3, 5 ] n = len(arr) print(countUnique(arr, n)) # This code is contributed by ankush_953
C#
// C# implementation of the approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
public class store : IComparer<KeyValuePair<int, int>>
{
public int Compare(KeyValuePair<int, int> x,
KeyValuePair<int, int> y)
{
if (x.Key != y.Key)
{
return x.Key.CompareTo(y.Key);
}
else
{
return x.Value.CompareTo(y.Value);
}
}
}
// Function to return the number
// of unique pairs in the array
static int countUnique(int []arr, int n)
{
// Set to store unique pairs
SortedSet<KeyValuePair<int,
int>> s = new SortedSet<KeyValuePair<int,
int>>(new store());
// Make all possible pairs
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
s.Add(new KeyValuePair<int, int>(arr[i], arr[j]));
// Return the size of the set
return s.Count;
}
// Driver code
public static void Main(string []arg)
{
int []arr = { 1, 2, 2, 4, 2, 5, 3, 5 };
int n = arr.Length;
Console.Write(countUnique(arr, n));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the number
// of unique pairs in the array
function countUnique(arr,n)
{
// Set to store unique pairs
let s = new Set();
// Make all possible pairs
for (let i = 0; i < n; i++)
for (let j = 0; j < n; j++)
s.add((arr[i], arr[j]));
// Return the size of the set
return 5*s.size;
}
// Driver code
let arr = [ 1, 2, 2, 4, 2, 5, 3, 5 ];
let n = arr.length;
document.write(countUnique(arr, n));
</script>
Producción:
25
Complejidad de tiempo: la complejidad de tiempo de la implementación anterior es O (n 2 Log n). Podemos optimizarlo a O (n 2 ) usando unordered_set con la función hash definida por el usuario .
Enfoque eficiente: primero averigüe la cantidad de elementos únicos en una array. Sea x el número de elementos únicos . Entonces, el número de pares únicos sería x 2 . Esto se debe a que cada elemento único puede formar un par con todos los demás elementos únicos, incluido él mismo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the number
// of unique pairs in the array
int countUnique(int arr[], int n)
{
unordered_set<int> s;
for (int i = 0; i < n; i++)
s.insert(arr[i]);
int count = pow(s.size(), 2);
return count;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 2, 4, 2, 5, 3, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countUnique(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the number
// of unique pairs in the array
static int countUnique(int arr[], int n)
{
HashSet<Integer> s = new HashSet<>();
for (int i = 0; i < n; i++)
{
s.add(arr[i]);
}
int count = (int) Math.pow(s.size(), 2);
return count;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 2, 4, 2, 5, 3, 5};
int n = arr.length;
System.out.println(countUnique(arr, n));
}
}
/* This code has been contributed
by PrinciRaj1992*/
Python3
# Python3 implementation of the approach # Function to return the number # of unique pairs in the array def countUnique(arr, n): s = set() for i in range(n): s.add(arr[i]) count = pow(len(s), 2) return count # Driver code if __name__ == "__main__" : arr = [ 1, 2, 2, 4, 2, 5, 3, 5 ] n = len(arr) print(countUnique(arr, n)) # This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the number
// of unique pairs in the array
static int countUnique(int []arr, int n)
{
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < n; i++)
{
s.Add(arr[i]);
}
int count = (int) Math.Pow(s.Count, 2);
return count;
}
// Driver code
static void Main()
{
int []arr = {1, 2, 2, 4, 2, 5, 3, 5};
int n = arr.Length;
Console.WriteLine(countUnique(arr, n));
}
}
// This code has been contributed by mits
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to return the number
// of unique pairs in the array
function countUnique(arr, n){
let s = new Set();
for (let i = 0; i < n; i++)
{
s.add(arr[i]);
}
let count = Math.pow(s.size, 2);
return count;
}
// Driver Code
let arr = [ 1, 2, 2, 4, 2, 5, 3, 5 ];
let n = arr.length;
document.write(countUnique(arr, n));
</script>
Producción:
25
Complejidad de tiempo: O(n)