Single non duplicate number in an array

Given an array with all elements repeated twice except one element find out that element.

Constraints:

The time complexity should be O(n)

Space complexity should be O(1)

For example:

Given the array :

[1,3,4,3,4]

the output is 1 since it occurs only once.

Try out the solution here:

https://leetcode.com/problems/single-number

Solution:

If we can use extra space the solution is easier.

Use a hashmap to store each number and a counter which keeps track of the number of times the element occurs in the array.

Scan the array once and increment the counter value when the same element occurs twice.

Once the counter values are populated , scan the hashmap keys and find the key with counter value 1 and return it.

The difficulty arises because of the constraint that you should not use any extra space. Space complexity should be O(1).

To solve this we can use bit manipulation.

We can use XOR operation in particular.

XOR operation when done between a bit and zero will return that bit but when done between the same bits will return 0.

So since numbers appear twice when they are XORed together it results in zero leaving behind the one number which is unique.

Here is the code:

class Solution {
    public int singleNumber(int[] nums) {
        
        int x = 0;
        
        
        for(int i:nums){
            
            x ^= i;
        }
        
        return x;
        
    }
}

We are not using any extra space here in proportion to the input so space complexity is O(1).

And we scan the array only once so time complexity is O(n).

Bit manipulation can often help in finding solutions faster and this is one such example.