[GFG][Amazon] Find the missing and repeating number

Problem: 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.

Example:

Input: arr[] = {3, 1, 3}
Output: Missing = 2, Repeating = 3
Explanation: In the array, 2 is missing and 3 occurs twice 

Input: arr[] = {4, 3, 6, 2, 1, 1}
Output: Missing = 5, Repeating = 1

Approach: We are going to use xor here.

Implementation in C++:

vector<int> findTwoElement(vector<int> arr, int n)

{

        // code here

        int xor1 = arr[0];

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

        {

            xor1 ^= arr[i];

        }

        

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

        {

            xor1 ^= i;

        }

        

        int setBit = xor1 & ~(xor1 - 1);

        int x = 0, y = 0;

        for (int i = 0; i < n; ++i)

        {

            if (arr[i] & setBit != 0)

            {

                x ^= arr[i];

            }

            else

            {

                y ^= arr[i];

            }

        }

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

        {

            if (i & setBit != 0)

            {

                x ^= i;

            }

            else

            {

                y ^= i;

            }   

        }

        vector<int> result;

        result.push_back(x);

        result.push_back(y);

        return result;

    }

Complexity: O(n)