Find Unique pair in an array with pairs of numbers
Given an array where every element appears twice except a pair (two elements). Find the elements of this unique pair.
Examples:
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
The idea is based on below post.
Find Two Missing Numbers | Set 2 (XOR based solution)
- XOR each element of the array and you will left with the XOR of two different elements which are going to be our result. Let this XOR be “XOR”
- Now find a set bit in XOR.
- Now divide array elements in two groups. One group that has the bit found in step 2 as set and other group that has the bit as 0.
- XOR of elements present in first group would be our first element. And XOR of elements present in second group would be our second element.
Implementation:
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> |
Output
The unique pair is (7, 5)
Time Complexity: O(n)
Auxiliary Space: O(1)
Contact Us