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

We can find the non-repeating number in an array where every other element repeats twice using bit manipulation. This can be achieved using the XOR bitwise operator.

The XOR operation ("exclusive or") is a binary operation that takes two bits and returns 1 if exactly one of the bits is 1. In other words, it returns true if the two bits are opposite.

The XOR operation has two properties which are very useful in this context:

1) ‘A XOR A = 0‘

2) ‘A XOR 0 = A‘

3) ‘A XOR B XOR A = B‘

If we XOR all elements in the array, all the elements which are repeated twice will become 0 (because ‘A XOR A = 0‘), and we are left with the element which is only present once as the result.

Suppose we have an array ‘arr[] = 2, 3, 5, 4, 5, 3, 4‘.

If we XOR all the numbers together:

‘(2 3̂ 5̂ 4̂ 5̂ 3̂ 4̂)‘

We can reorder as:

‘((2 2̂) (̂3 3̂) (̂4 4̂) (̂5 5̂)) 5̂‘

Each pair of the same number will XOR to 0, leaving us with:

‘0 5̂‘

Remember ‘A XOR 0 = A‘, therefore we get ‘5‘ which is the number that has no duplicate in the array.

A Python example code:

def find_single(nums):
    res = 0
    for num in nums:
        res ^= num
    return res

For an array ‘arr[] = 2, 3, 5, 4, 5, 3, 4‘, calling ‘find_single(arr)‘ would return ‘5‘.