Problem Statement

Given a non-empty array of integers, every element appears twice except for one. Find that single one.


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

Example 1:

Input: [2,2,1]
Output: 1
Example 2:

Input: [4,1,2,1,2]
Output: 4

Solution Explanation

The question here is very simple. It already provided some details like, we are going to only deal with positive numbers and it also mentioned that except for one, every other element is going to appear twice. We can do brute force or we can use map or set but our question specifically mentioned to not use extra space.

What if we use XOR ? The basic idea of using XOR operation is a^c^c =a, which means two xor operations with the same number will eliminate the number by becoming zero and we will be left with a single number which does not have duplicate.

class Solution {
    public int singleNumber(int[] nums) {
        int xor=0;
        for(int i=0;i<nums.length;i++){
            xor = xor ^ nums[i];
        return xor;

Explanation why this technique works:
Let's say our given array is : [4,1,2,1,2]. This is what we are doing in our code above:
The for loop produces the below output.
=> xor = 4 ^ 1 ^ 2 ^ 1 ^ 2
=> xor = 4 ^ 1 ^ 1 ^ 2 ^ 2  (Rearranging by taking same numbers together, this happens internally, Just FYI)
=> xor = 4 ^ 0 ^ 0 (Same numbers become zero, this happens internally, Just FYI)
=> xor = 4

Time Complexity                                                                                                        We are iterating through the given array once using the for loop, so time complexity is going to  be : O(n) which is linear runtime.

Space Complexity                                                                                                       We are not storing data anywhere here so our space complexity is : 0(1).