Algorithms and Me: Curious case of Missing and Repeating elements

Algorithms and Me: Curious case of Missing and Repeating elements
Give an array of size N, it contains all numbers from 1 to N-1 except one. Find the missing number.

int missing_number(int a[], int n, int size){

int xor =0;

int i;

for(i=0; i<size; i++)

xor = xor^a[i];

for(i=1; i<=n; i++)

xor = xor^i;

return xor;

}

Given an array of size N, it contains all numbers from 1 to N-2 except one which is repeated twice. Find the repeated number.

int repeating_number(int a[], int n, int size){

int xor =0;

int i;

for(i=0; i<size; i++)

xor = xor^a[i];

for(i=1; i<=n; i++)

xor = xor^i;

return xor;

}

Given an array of size N, which contains number ranging from 1 to N-1 has one missing and one repeating number. Find repeated and missing number.
Xor all numbers in array and 1 to N, the result contains two numbers XORed, one missing and other repeating.
Now we need split them.
So again go back to our array and numbers from 1 to N-1 and 0 to size and XOR numbers in two buckets, one buckets contains XOR result of XORing all numbers with given bit set and other bucket contains XOR result of XORing all numbers with given bit reset.

int missing_and_repeating(int a[], int n, int size){

int xor =0;

int i;

int x =0 , y =0;

for(i=0; i<size; i++)

xor = xor^a[i];

for(i=1; i<=n; i++)

xor = xor^i;

// Get the rightmost bit which is set

int set_bit_no =  xor & ~(xor -1);

// XOR numbers in two buckets

for(i=0; i<size; i++){

if(a[i]& set_bit_no){

x = x^a[i];

}

else

y = y^ a[i];

}

for(i=1; i<=n; i++){

if(i & set_bit_no)

x = x^i;

else

y = y^i;

}

printf("\n %d %d ", x,y );

}

Read full article from Algorithms and Me: Curious case of Missing and Repeating elements