Algorithm {Single Number}

We are working on next task from leetcode. So, next task will be …. , {Single Number} 🙂.

Task:

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Stop and think …

What we have, input array of integers and we should find one NOT DUPLICATE number. So, it’s easy … Go to the math knowledge and try to remember XOR if you don’t remember you can try to refresh knowledge in XOR Truth Table. So, main idea that two equal numbers will return 0. What does it mean ??? If we have array like next

1,1,4,4,5

And try to XOR all values we will get 5, OK, that is very good and we can start use that functionality to develop our algorithm.

Lets go :

public int singleNumber(int[] A) {
        int result = 0;
        for(int i = 0; i < A.length; i ++){
            result^=A[i];
        }
        return result;
}

OK, what we can see, we have result value, and one loop all values are XORed to the result (read about XOR functionality) so after the loop we will have Single number …That is perfect 🙂

OK, What  is the complexity, as you can see, we have just a one loop , so, complexity will be O(N), as we are using just a one int variable it means we do not use extra memory … Perfect, we solved that task …

Cheers ! 🙂