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
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
}
http://yuanhsh.iteye.com/blog/2185879voidprintRepeating(intarr[],intsize){inti;for(i = 0; i < size; i++){if(arr[abs(arr[i])] > 0)arr[abs(arr[i])] = -arr[abs(arr[i])];elseprintf(" %d ",abs(arr[i]));}}
- void findRepeating(int arr[], int size) {
- int i;
- printf("\n The repeating elements are");
- 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]));
- }
- }
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.
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);} http://yuanhsh.iteye.com/blog/2185879- public void findTwoRepeatingNumbers(int[] A) {
- int x = 0;
- for(int i=0; i<A.length; i++) {
- int j = (i!=A.length-1) ? i : 0;
- x ^= A[i] ^ j;
- }
- int lsb = x & -x;
- int a = 0, b = 0;
- for(int i=0; i<A.length; i++) {
- if((A[i]&lsb) == lsb) {
- a ^= A[i];
- } else {
- b ^= A[i];
- }
- int j = (i!=A.length-1) ? i : 0;
- if((j&lsb) == lsb) {
- a ^= j;
- } else {
- b ^= j;
- }
- }
- System.out.println("a="+a + ", b="+b);
- }
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!
XY = P/n!
X – Y = sqrt((X+Y)^2 – 4*XY)
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);}Method 1 (Use Count array)
Time Complexity: O(n)
Auxiliary Space: O(n)
- void findRepeating(int arr[], int size) {
- int *count = (int *)calloc(sizeof(int), (size - 2));
- int i;
- printf(" Repeating elements are ");
- for(i = 0; i < size; i++) {
- if(count[arr[i]] == 1)
- printf(" %d ", arr[i]);
- else
- count[arr[i]]++;
- }
- }
Read full article from Find the two repeating elements in a given array | GeeksforGeeks
