Missing and repeating number in an array

Given an unsorted array of size n with numbers ranging from 1 to n. One number from set {1, 2, 3, …, n} is missing and one number occurs twice in array. For example: If the size is 6, then array may be

    int arr[] = {1, 5, 3, 4, 1, 2};

Where 1 is repeating twice and 6 is missing.
Write code to find the two numbers (one which is missing and one which is repeating).
Solutions:

Obviously, there are multiple solutions to this problem. Lets take them one-by-one:

Method-1: (Use Sorting)

One of the basic (least optimized) solution is to sort the array and find the numbers.

Time taken: O(n.lg(n)
Extra Space required: Constant

Method-2:(Using Hash)

We can use an extra array of size n which will store the count of occurrences of i at i’th position in the array. In this case we need to traverse the array only once (and then we need to traverse the auxiliary array also)

Time taken: O(n)
Extra Space Required: O(n)

Method-3: (Using XOR)

This is the best solution, and I could not resist writing this blog because of this solution only:

Let the given array be

    int arr[] = {1, 5, 3, 4, 1, 2};

Let us take XOR of all the elements in the array

    xor = arr[0] ^ arr[1] ^ arr[2] ^ arr[3] ^ arr[4] ^ arr[5];

Now xor all the elements from 1 to n with the above xor

    xor = xor ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6;

The final alue in the xor (after above operations) will be the XOR of the missing number (i.e 6) and repeating number (i.e 1). All other elements will nullify themselves.

Lets call the missing number as x and repeating number as y. So, in effect, we will get

    xor = x ^ y;

All the bits that are set in xor will be either set in x or y (but not both). So if we take any set-bit (lets take the rightmost set-bit for this example, but you can take any) and divide the elements of array in 2 sets A & B

A: Set of elements for which the bit is set
B: Set of elements in the given array for which the bit is NOT set

From our example:

    xor = 1 ^ 6 = 111 (in binary)

Lets divide the elements on the basis of LSB set

A = {1, 5, 3, 1}
B = {4, 2}

Note: If a number is repeated, then we are keeping it twice (different from the definition of set in Maths.

Now also divide elements from 1 to n on the same basis as above (whether, the rightmost bit set in xor is set or not). The 2 sets will become:

A = {1, 5, 3, 1, 1, 3, 5}
B = {4, 2, 2, 4, 6}

Now if we XOR all the elements of set A we will get 1 (i.e x) and if we XOR all the elements of B we will get 6 (i.e y)

Hence the result. The time & Space complexities of this approach are amazingly good.

Time taken: O(n)
Extra Space Required: Constant

Here is the function, which will print repeating number and missing number in an array:

    /** the array arr should have numbers from 1 to n only with exactly one number missing
     * and one repeating, only once.
     */
    void getMissingAndRepeating(int arr[], int n)
    {
       int xors = 0;
       int i;
       int x = 0;
       int y = 0;
       // XOR of all elements in the array
       for(i=0; i<n; i++)
          xors = xors ^ arr[i];
       // XOR of numbers from 1 to n (with xor)
       for(i=1; i<=n; i++)
          xors = xors ^ i;
       // Number with the same bit set as the rightmost set bit in xor
       int setBitNum = xors & ~ (xors-1);
       // Dividing the numbers in two sets and also getting the XORs
       for(i = 0; i < n; i++)
       {
          if(arr[i] & setBitNum)
               x = x ^ arr[i];  // arr[i] belongs to Set A
          else
               y = y ^ arr[i];  // arr[i] belongs to Set B
       }
       for(i = 1; i <= n; i++)
       {
          if(i & setBitNum)
              x = x ^ i;  // arr[i] belongs to Set A
          else
              y = y ^ i;  // arr[i] belongs to Set B
       }
       cout << "Repeating Number : "<< x << std::endl
            << "Missing Number : "<< y;
    }
    int main()
    {
       int arr[6] = {1, 2, 3, 1, 4, 5};
       getMissingAndRepeating(arr, 6);
       return (0);
    }