2. Numbers that appear only once

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once. Note: Your algorithm should have linear time complexity. Can you do it without using extra space?

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        returnsingle; }}Copy the code

The answer is xOR using bit arithmetic.

• Commutative law: A ^ b ^ c <=> A ^ c ^ b
• Any number at 0 or any number 0 to the n => n
• The same number is either 0: n ^ n => 0