Find the repeating and the missing | Added 3 new methods | C ++ program to Find the repeating and missing elements ; The output of this function is stored at * x and * y ; Will hold xor of all elements and numbers from 1 to n ; Will have only single set bit of xor1 ; Get the xor of all array elements ; XOR the previous result with numbers from 1 to n ; Get the rightmost set bit in set_bit_no ; Now divide elements into two sets by comparing a rightmost set bit of xor1 with the bit at the same position in each element . Also , get XORs of two sets . The two XORs are the output elements . The following two for loops serve the purpose ; arr [ i ] belongs to first set ; arr [ i ] belongs to second set ; i belongs to first set ; i belongs to second set ; * x and * y hold the desired output elements ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void getTwoElements ( int arr [ ] , int n , int * x , int * y ) { int xor1 ; int set_bit_no ; int i ; * x = 0 ; * y = 0 ; xor1 = arr [ 0 ] ; for ( i = 1 ; i < n ; i ++ ) xor1 = xor1 ^ arr [ i ] ; for ( i = 1 ; i <= n ; i ++ ) xor1 = xor1 ^ i ; set_bit_no = xor1 & ~ ( xor1 - 1 ) ; for ( i = 0 ; i < n ; i ++ ) { if ( arr [ i ] & set_bit_no ) * x = * x ^ arr [ i ] ; else * y = * y ^ arr [ i ] ; } for ( i = 1 ; i <= n ; i ++ ) { if ( i & set_bit_no ) * x = * x ^ i ; else * y = * y ^ i ; } } int main ( ) { int arr [ ] = { 1 , 3 , 4 , 5 , 5 , 6 , 2 } ; int * x = ( int * ) malloc ( sizeof ( int ) ) ; int * y = ( int * ) malloc ( sizeof ( int ) ) ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; getTwoElements ( arr , n , x , y ) ; cout << " ▁ The ▁ missing ▁ element ▁ is ▁ " << * x << " ▁ and ▁ the ▁ repeating " << " ▁ number ▁ is ▁ " << * y ; getchar ( ) ; }