Monday, October 3, 2011

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


void findDup(int* arr, int n, int& x, int& y) // x and y will be our result
{
    int xor = 0;
    for(int i=1; i<=n; xor^=i++);
    for(i=0; i<n+2; xor^=arr[i++]);
    int setBit = xor & ~(xor -1);
    for(i=0;i<n+2;++i)
        (arr[i] & setBit) ? (x ^= arr[i]) : (y ^= arr[i]);
    for(i=1; i<=n; ++i)
        (i & setBit) ? (x ^= i) : (y ^= i);   
}

No comments:

Post a Comment