Find the two repeating elements in a given array | Java code to Find the two repeating elements in a given array ; Will hold xor of all elements ; Will have only single set bit of xor ; Get the xor of all elements in arr [ ] and { 1 , 2 . . n } ; Get the rightmost set bit in set_bit_no ; Now divide elements in two sets by comparing rightmost set bit of xor with bit at same position in each element . ; XOR of first set in arr [ ] ; XOR of second set in arr [ ] ; XOR of first set in arr [ ] and { 1 , 2 , ... n } ; XOR of second set in arr [ ] and { 1 , 2 , ... n } ; Driver program to test the above function
class RepeatElement { void printRepeating ( int arr [ ] , int size ) { int xor = arr [ 0 ] ; int set_bit_no ; int i ; int n = size - 2 ; int x = 0 , y = 0 ; for ( i = 1 ; i < size ; i ++ ) xor ^= arr [ i ] ; for ( i = 1 ; i <= n ; i ++ ) xor ^= i ; set_bit_no = ( xor & ~ ( xor - 1 ) ) ; for ( i = 0 ; i < size ; i ++ ) { int a = arr [ i ] & set_bit_no ; if ( a != 0 ) x = x ^ arr [ i ] ; else y = y ^ arr [ i ] ; } for ( i = 1 ; i <= n ; i ++ ) { int a = i & set_bit_no ; if ( a != 0 ) x = x ^ i ; else y = y ^ i ; } System . out . println ( " The ▁ two ▁ reppeated ▁ elements ▁ are ▁ : " ) ; System . out . println ( x + " ▁ " + y ) ; } public static void main ( String [ ] args ) { RepeatElement repeat = new RepeatElement ( ) ; int arr [ ] = { 4 , 2 , 4 , 5 , 2 , 3 , 1 } ; int arr_size = arr . length ; repeat . printRepeating ( arr , arr_size ) ; } }