using System;

using System.Linq;

using System.Collections.Generic;

using System.Text;

​

/*

​

**************** This is optimized Solution *****************

​

Link: [https://www.scaler.com/academy/mentee-dashboard/class/28334/assignment/problems/9184?navref=cl_tt_nv]

​

Problem Description:

Given an array of positive integers A, two integers appear only once, and all the other integers appear twice.

Find the two integers that appear only once.

​

​

​

Problem Constraints

2 <= |A| <= 100000

1 <= A[i] <= 109

​

​

​

Input Format

The first argument is an array of integers of size N.

​

​

​

Output Format

Return an array of two integers that appear only once.

​

​

​

Example Input

Input 1:

A = [1, 2, 3, 1, 2, 4]

Input 2:

​

A = [1, 2]

​

​

Example Output

Output 1:

[3, 4]

Output 2:

​

[1, 2]

​

​

Example Explanation

Explanation 1:

3 and 4 appear only once.

Explanation 2:

​

1 and 2 appear only once.

​

*/

public class Program

{

    private static int findXOR(List<int> A)

    {

        int _arrCount = A.Count;

        int _XorVal = 0;

        for(var i = 0; i < _arrCount; i++){

            _XorVal ^= A[i];

        }

        return _XorVal;

    }

    private static int CheckBit(int N, int i){

        return (N >> i) & 1;

    }

    private static List<int> getUniqueNumbers(List<int> A){

        int _xorVal = Program.findXOR(A);

        List<int> _uniqueElemList = new List<int>();

        int _setGrp = 0; int _unSetGrp = 0;

        int _setBitPosition = 0;

        /*

        * For Loop to check which nth bit is set.

        */

        for(int j = 0; j < 32; j++){

            if(Program.CheckBit(_xorVal, j) == 1){

                _setBitPosition = j;

                break;

            }

        }

        /*

        * For Loop to iterate array elements and segerate based on the bit position "_setBitPosition"  

        */

        for(var k = 0; k < A.Count; k++){

            if(Program.CheckBit(A[k], _setBitPosition) == 1){

                _setGrp ^= A[k];

            }else{

                _unSetGrp ^= A[k];

            }

        }

        _uniqueElemList.Add(_setGrp);

        _uniqueElemList.Add(_unSetGrp);

        _uniqueElemList.Sort();

        return _uniqueElemList;

    }

    public static void Main()

    {

        //List<int> elem = new List<int>() { 5, 4, 1, 4, 5, 6 };

        //List<int> elem = new List<int>() { 1, 2, 3, 1, 2, 4 };

        List<int> elem = new List<int>() { 1, 2 };

        List<int> _uniqueElems = Program.getUniqueNumbers(elem);

        Console.WriteLine("The Unique elements are: " + string.Join(" ", _uniqueElems));

    }

}