Can you find the two non-repeating numbers in an array where every element repeats twice except two, using bit manipulation?

You can find two non-repeating numbers in an array where every other element repeats twice except two. This can be achieved through bit manipulation, one of the key ideas behind the XOR operation. Here is how you can do it step by step.

1. Take XOR of all the elements in the array. XOR of all elements in array will give XOR of the two non-repeating elements, which we’ll call xXory. Since we are XORing same numbers twice, they will cancel out each other, and non repeating numbers XOR will remain.

For instance, consider the array: 2, 4, 7, 9, 2, 4. The XOR of all elements yields ‘79̂‘.

2. Take any set bit (bit that is 1) of xXory and divide the elements of array into two groups. One group which has the same bit set and another group which has this bit unset. We can take any set bit, let’s say kth bit from right. One non-repeating number will belong to the first group and the other non-repeating number will be in the second group. By performing XOR operation on the two groups individually, we get the two numbers.

For example, let’s say 1st bit from right of ‘79̂‘ is set. Divide array into two groups and do XOR on elements. Group1: 2, 7, 2 => ‘27̂2̂‘ gives 7 which is one of the non-repeating number. Group2: 4, 9, 4 => ‘49̂4̂‘ gives 9 which is the other non-repeat number.

Here’s the Python code snippet for better understanding:

def findTwoNonRepeatingNumbers(arr):
    xor = arr[0]
    for i in range(1, len(arr)):
        xor ^= arr[i]

    setBitNo = xor & ~(xor-1)
  
    x, y = 0, 0
    for i in range(len(arr)):
        if((arr[i] & setBitNo) != 0):
            x = x ^ arr[i]
        else:
            y = y ^ arr[i]
            
    return x, y

arr = [2, 3, 7, 9, 11, 2, 3, 11]
print(findTwoNonRepeatingNumbers(arr))

This code first takes XOR of all elements, gets the last set bit of ‘xor‘ and separates these two non-repeating numbers(x, y) into two groups based on last set bit. Performing XOR on these two groups separately gives these two numbers.

The complexity of this solution is O(n), which is the best we can achieve for this problem.

Please note this method only works when there are exactly two non-repeating elements. Other cases require different handling.