Problem Statement – Given an array of numbers where all numbers appear twice except for one number which appears only once, find that number.

Clues –

• Solution should be O(N) in time and O(1) in space.
• Use bit operations.

Solution – XOR of two same numbers is zero. So, if we take the XOR of all numbers in the array, the numbers which appear twice will get cancelled and in the end the number which is left would be our number which had appeared only once. Example –

• 2 ^ 2 = 0
• 2 ^ 2 ^ 3 = 3
• 2 ^ 3 = 1
• 1 ^ 2 = 3
• 1 ^ 3 = 2
• 2 ^ 3 ^ 2 = 3
• 2 ^ 3 ^ 3 = 2

This solution would be O(N) in time and O(1) in space.

Code –

int findNonDuplicate(int arr[], int n)
{
    int xorVal = 0, i;
     
    // XOR all the elements
    for (i = 0; i < n; ++i) {
        xorVal ^= arr[i];
    }
     
    return xorVal;
}