#         
## Problem Statement

We have 2*`N` +2 numbers. In this expression, every number comes twice except two numbers which occur once.

Find these two numbers.

## Pre-Requisites

- [XOR and its properties](https://www.educative.io/answers/what-is-the-xor-bitwise-operator).

## Problem Explanation
Let two numbers that occur once be `a` and `b`. The array be a list of 2*`N`+2 numbers.


     
  1. `N`=2, `array` = [2, 1, 3, 5, 1, 3]
      
      - In this example, {1, 3} occur twice and {2, 5} occur once.
       
      -  Thus, `a` = 2 and `b` = 5

  2. `N` =3, `array` = [1, 10, 10, 1, 5, 6, 5, 9]

     - `a` = 6

     - `b` = 9

## Solution 

Let `a` and `b` be the two unique numbers.

We'll first calculate the res and cumulative XOR of the array.

We know that the XOR of any number occurring even times is 0. Moreover, every number except `a` and `b` occur twice.

Thus, effectively `res` = `a`^`b`.

Now, a fundamental observation is:

- We know, res = `a` ^ `b`.

> **Note**: If the `i`th bit of `res` is set, the `i`th bit of `a` and the `i`th bit of `b` must be different.





We’ll split the main array into two arrays (`array1` and `array2`).

   - `array1` = List of numbers of `array` which have their `i`th bit same as `i`th bit of `a`.

   - `array2` = List of numbers of `array` which have their `i`th bit same as `i`th bit of `b`.

The cumulative XOR of `array1` will give us the value of `a`, and the cumulative XOR of `array2` will provide us with the value of `b`.



N = 3
array = [1, 10, 10, 1, 5, 6, 5, 9]

a,b = 0,0
res = 0
for v in array:
    res = res^v

lsb = 0
while (True):
    if ((res>>lsb)&1): break
    lsb+=1


for v in array:
    if ((v>>lsb)&1): a^=v
    else: b^=v

print(a,b)




## Explanation
- Line 1: We take `N` as input.
- Line 2: We take 2*`N`+2 numbers as input and store them in an `array`.
- Lines 3–4: We initialize two unique numbers (`a`,`b`) and cumulative XOR of `array` and `res` to `0`.
- Line 6: We loop over every value `v` of the array to calculate `res`.
- Line 9: We initialize `lsb` (the least significant bit) to `0`.
- Lines 10–12: We start the `while` loop to calculate `lsb` of `res`.
- Lines 15–17: We loop over every value `v` of the `array`.

    - Line 16: If the `lsb`th bit of `v` is set, then we perform `a = a^v`, since we want `a` to be the cumulative XOR of all numbers in array with their `lsb` bit set.

  - Line 17: If the `lsb`th bit of `v` is off, then `b = b^v`.
- Line 19: Consequently, the first unique number will be `a`, and the second unique number will be `b`. 


How to find two non-repeating numbers in an array

Use XOR to find two unique numbers in an array where every other number appears twice.