The single element problem

I’m doing some algorithm practices recently in Leetcode. This post is about the “Single Number” problem and my attempts to it.

In this problem, you are given an array with some int numbers in pair except one single number and you need to find the single number. The tricky part I think is that you can’t delete an element from an array directly in java so you need to fine another approach to make the single element more “outstanding”.

My first attempt is quite straightforward (and stupid): use a for loop to find the maximum number in the given array and plus it by 1 to generate an invalid number, then use another 2 loops to find elements in pair and turn them into this invalid number. At last, use another loop to find the element which doesn’t equal to the invalid number to get the result. This approach did solve the problem, but the speed is pathetically slow and unsurprisingly, it failed the speed test.

My second attempt got rid of the loop for generating invalid number and the loop for finding the element which is not “invalid”. Instead, I use a variable named “counter”, the counter will become 1 when an element has a duplicate when its “duplicate checking” loop ends, and the counter will be reset to 0 before next checking loop. If an element doesn’t have a duplicate, the counter will still be 0 and the answer will be nums[i], then the program will jump out of the loop directly. Here’s this version’s solution:

class Solution {
    public int singleNumber(int[] nums) {
        int answer = 0;
        int counter = 0;

        for (int i = 0; i < nums.length; i++){
            for (int j = 0; j < nums.length; j++){
                if (nums[i]==nums[j] && i!=j){
                    counter++;
                }
            }
            if (counter == 1){
                counter = 0;
            } else {
                answer = nums[i];
                break;
            }
        }

        return answer;
    }
}

This solution passed the time limited test in most cases but still failed sometimes. Obviously this solution is not fast enough because the two loops for duplicate checking. But I couldn’t figure out a better solution. So I checked the discussion posts of this problem and find a much more better solution than mine:

    int ans =0;
    int len = nums.length;
    for(int i=0; i<len; i++){
        ans ^= nums[i];
    }

    return ans;

This solution uses only one loop and the way it check unduplicated element is using bitwise XOR. The main idea is that 0^N==N and N^N==0. Also, XOR is commutative which means N1^N3^N2^N1^N2 == N1^N1^N2^N2^N3. As a result, the variable ans will always be the single element and the complexity is only O(n)! Brilliant!