Find the two repeating elements in a given array | GeeksforGeeks

You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.

For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5

Method 5 (Use array elements as index)

Traverse the array. Do following for every index i of A[].
{
check for sign of A[abs(A[i])] ;
if positive then
   make it negative by   A[abs(A[i])]=-A[abs(A[i])];
else  // i.e., A[abs(A[i])] is negative
   this   element (ith element of list) is a repetition
}

void printRepeating(int arr[], int size)

{

  int i;  

     

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

  {

    if(arr[abs(arr[i])] > 0)

      arr[abs(arr[i])] = -arr[abs(arr[i])];

    else

      printf(" %d ", abs(arr[i]));

  }         

} 

Method 4 (Use XOR)

The approach used here is similar to method 2 of this post.
Let the repeating numbers be X and Y, if we xor all the elements in the array and all integers from 1 to n, then the result is X xor Y.
The 1’s in binary representation of X xor Y is corresponding to the different bits between X and Y. Suppose that the kth bit of X xor Y is 1, we can xor all the elements in the array and all integers from 1 to n, whose kth bits are 1. The result will be one of X and Y.

void printRepeating(int arr[], int size)

{

  int xor = arr[0]; /* Will hold xor of all elements */

  int set_bit_no;  /* Will have only single set bit of xor */

  int i;

  int n = size - 2;

  int x = 0, y = 0;

   

  /* Get the xor of all elements in arr[] and {1, 2 .. n} */

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

    xor ^= arr[i]; 

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

    xor ^= i;  

 

  /* Get the rightmost set bit in set_bit_no */

  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. */

  for(i = 0; i < size; 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[] */

  }

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

  {

    if(i & set_bit_no)

      x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/

    else

      y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */

  }

   

  printf("\n The two repeating elements are %d & %d ", x, y);

} 




Method 3 (Make two equations)

Let summation of all numbers in array be S and product be P

X + Y = S – n(n+1)/2
XY = P/n!

X – Y = sqrt((X+Y)^2 – 4*XY)

There can be addition and multiplication overflow problem with this approach.

void printRepeating(int arr[], int size)

{

  int S = 0;  /* S is for sum of elements in arr[] */

  int P = 1;  /* P is for product of elements in arr[] */ 

  int x,  y;   /* x and y are two repeating elements */

  int D;      /* D is for difference of x and y, i.e., x-y*/

  int n = size - 2,  i;

 

  /* Calculate Sum and Product of all elements in arr[] */

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

  {

    S = S + arr[i];

    P = P*arr[i];

  }       

   

  S = S - n*(n+1)/2;  /* S is x + y now */

  P = P/fact(n);         /* P is x*y now */

   

  D = sqrt(S*S - 4*P); /* D is x - y now */

   

  x = (D + S)/2;

  y = (S - D)/2;

   

  printf("The two Repeating elements are %d & %d", x, y);

}

Read full article from Find the two repeating elements in a given array | GeeksforGeeks