Single Number

• LeetCode: Single Number
• Problem:

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?

• Analysis:

Use the xor notation to solve this problem.

XOR Truth Table:
                 -----------------
                 | x | y | x ^ y |
                 ----------------- 
                 | 0 | 0 |   0   |
                 -----------------
                 | 0 | 1 |   1   |
                 -----------------
                 | 1 | 0 |   1   |
                 -----------------
                 | 1 | 1 |   0   |
                 -----------------

As a result, the duplicate numbers will be 0 via xor operator. 

Only the single number will be left.

• Code - Java:

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

• Code - C++:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        int len = nums.size();
        for (int i = 0; i < len; i++) {
            result ^= nums[i];
        }
        return result;
    }
};

• Code - Python:

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = 0
        for num in nums:
            result ^= num
        return result

• Code - C:

int singleNumber(int* nums, int numsSize) {
    int result = 0;
    for (int i = 0; i < numsSize; i++) {
        result ^= nums[i];
    }
    return result;
}

• Time Complexity: O(N), N is the length of array
• Space Complexity: O(1)