Dada una array donde cada elemento aparece dos veces excepto un par (dos elementos). Encuentra los elementos de este par único.
Ejemplos:
Input : 6, 1, 3, 5, 1, 3, 7, 6 Output : 5 7 All elements appear twice except 5 and 7 Input : 1 3 4 1 Output : 3 4
La idea se basa en la siguiente publicación.
Encuentra dos números que faltan | Conjunto 2 (solución basada en XOR)
- XOR cada elemento de la array y quedará con el XOR de dos elementos diferentes que serán nuestro resultado. Sea este XOR “ XOR ”
- Ahora encuentre un bit establecido en XOR .
- Ahora divida los elementos de la array en dos grupos. Un grupo que tiene el bit encontrado en el paso 2 como establecido y otro grupo que tiene el bit como 0.
- XOR de elementos presentes en el primer grupo sería nuestro primer elemento. Y XOR de elementos presentes en el segundo grupo sería nuestro segundo elemento.
Implementación:
C++
// C program to find a unique pair in an array
// of pairs.
#include <stdio.h>
void findUniquePair(int arr[], int n)
{
// XOR each element and get XOR of two unique
// elements(ans)
int XOR = arr[0];
for (int i = 1; i < n; i++)
XOR = XOR ^ arr[i];
// Now XOR has XOR of two missing elements. Any set
// bit in it must be set in one missing and unset in
// other missing number
// Get a set bit of XOR (We get the rightmost set bit)
int set_bit_no = XOR & ~(XOR-1);
// Now divide elements in two sets by comparing rightmost
// set bit of XOR with bit at same position in each element.
int x = 0, y = 0; // Initialize missing numbers
for (int i = 0; i < n; i++)
{
if (arr[i] & set_bit_no)
x = x ^ arr[i]; /*XOR of first set in arr[] */
else
y = y ^ arr[i]; /*XOR of second set in arr[] */
}
printf("The unique pair is (%d, %d)", x, y);
}
// Driver code
int main()
{
int a[] = { 6, 1, 3, 5, 1, 3, 7, 6 };
int n = sizeof(a)/sizeof(a[0]);
findUniquePair(a, n);
return 0;
}
Java
// Java program to find a unique pair
// in an array of pairs.
class GFG
{
static void findUniquePair(int[] arr, int n)
{
// XOR each element and get XOR of two
// unique elements(ans)
int XOR = arr[0];
for (int i = 1; i < n; i++)
XOR = XOR ^ arr[i];
// Now XOR has XOR of two missing elements.
// Any set bit in it must be set in one
// missing and unset in other missing number
// Get a set bit of XOR (We get the
// rightmost set bit)
int set_bit_no = XOR & ~(XOR-1);
// Now divide elements in two sets by
// comparing rightmost set bit of XOR with
// bit at same position in each element.
// Initialize missing numbers
int x = 0, y = 0;
for (int i = 0; i < n; i++)
{
if ((arr[i] & set_bit_no)>0)
/*XOR of first set in arr[] */
x = x ^ arr[i];
else
/*XOR of second set in arr[] */
y = y ^ arr[i];
}
System.out.println("The unique pair is (" +
x + "," + y + ")");
}
// Driver code
public static void main (String[] args) {
int[] a = { 6, 1, 3, 5, 1, 3, 7, 6 };
int n = a.length;
findUniquePair(a, n);
}
}
/* This code is contributed by Mr. Somesh Awasthi */
Python 3
# Python 3 program to find a unique
# pair in an array of pairs.
def findUniquePair(arr, n):
# XOR each element and get XOR
# of two unique elements(ans)
XOR = arr[0]
for i in range(1, n):
XOR = XOR ^ arr[i]
# Now XOR has XOR of two missing
# elements. Any set bit in it
# must be set in one missing and
# unset in other missing number
# Get a set bit of XOR (We get
# the rightmost set bit)
set_bit_no = XOR & ~(XOR - 1)
# Now divide elements in two sets
# by comparing rightmost set bit
# of XOR with bit at same position
# in each element.
x = 0
y = 0 # Initialize missing numbers
for i in range(0, n):
if (arr[i] & set_bit_no):
# XOR of first set in
# arr[]
x = x ^ arr[i]
else:
# XOR of second set
# in arr[]
y = y ^ arr[i]
print("The unique pair is (", x,
", ", y, ")", sep = "")
# Driver code
a = [6, 1, 3, 5, 1, 3, 7, 6 ]
n = len(a)
findUniquePair(a, n)
# This code is contributed by Smitha.
C#
// C# program to find a unique pair
// in an array of pairs.
using System;
class GFG {
static void findUniquePair(int[] arr, int n)
{
// XOR each element and get XOR of two
// unique elements(ans)
int XOR = arr[0];
for (int i = 1; i < n; i++)
XOR = XOR ^ arr[i];
// Now XOR has XOR of two missing
// elements. Any set bit in it must
// be set in one missing and unset
// in other missing number
// Get a set bit of XOR (We get the
// rightmost set bit)
int set_bit_no = XOR & ~(XOR - 1);
// Now divide elements in two sets by
// comparing rightmost set bit of XOR
// with bit at same position in each
// element. Initialize missing numbers
int x = 0, y = 0;
for (int i = 0; i < n; i++)
{
if ((arr[i] & set_bit_no) > 0)
/*XOR of first set in arr[] */
x = x ^ arr[i];
else
/*XOR of second set in arr[] */
y = y ^ arr[i];
}
Console.WriteLine("The unique pair is ("
+ x + ", " + y + ")");
}
// Driver code
public static void Main ()
{
int[] a = { 6, 1, 3, 5, 1, 3, 7, 6 };
int n = a.Length;
findUniquePair(a, n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find a
// unique pair in an array
// of pairs.
function findUniquePair($arr, $n)
{
// XOR each element and
// get XOR of two unique
// elements(ans)
$XOR = $arr[0];
for ($i = 1; $i < $n; $i++)
$XOR = $XOR ^ $arr[$i];
// Now XOR has XOR of two
// missing elements. Any set
// bit in it must be set in
// one missing and unset in
// other missing number
// Get a set bit of XOR
// (We get the rightmost set bit)
$set_bit_no = $XOR & ~($XOR-1);
// Now divide elements in two
// sets by comparing rightmost
// set bit of XOR with bit at
// same position in each element.
// Initialize missing numbers
$x = 0;
$y = 0;
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] & $set_bit_no)
// XOR of first set in arr[]
$x = $x ^ $arr[$i];
else
// XOR of second set in arr[]
$y = $y ^ $arr[$i];
}
echo"The unique pair is ", "(",$x," ", $y,")";
}
// Driver code
$a = array(6, 1, 3, 5, 1, 3, 7, 6);
$n = count($a);
findUniquePair($a, $n);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find a unique pair
// in an array of pairs.
function findUniquePair(arr, n)
{
// XOR each element and get XOR of two
// unique elements(ans)
let XOR = arr[0];
for (let i = 1; i < n; i++)
XOR = XOR ^ arr[i];
// Now XOR has XOR of two missing elements.
// Any set bit in it must be set in one
// missing and unset in other missing number
// Get a set bit of XOR (We get the
// rightmost set bit)
let set_bit_no = XOR & ~(XOR-1);
// Now divide elements in two sets by
// comparing rightmost set bit of XOR with
// bit at same position in each element.
// Initialize missing numbers
let x = 0, y = 0;
for (let i = 0; i < n; i++)
{
if ((arr[i] & set_bit_no)>0)
/*XOR of first set in arr[] */
x = x ^ arr[i];
else
/*XOR of second set in arr[] */
y = y ^ arr[i];
}
document.write("The unique pair is (" +
x + "," + y + ")" + "<br/>");
}
// driver function
let a = [ 6, 1, 3, 5, 1, 3, 7, 6 ];
let n = a.length;
findUniquePair(a, n);
</script>
Producción
The unique pair is (7, 5)
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Dhiman Mayank . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA