136.md

136. Single Number

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?

Thinking Process

1. Use XOR to add up all the numbers in the array
2. Numbers appears in pair will cancel out to 0, leaving the single element behind

public int singleNumber(int[] nums) {
    int singleNum = 0;
    for(int n : nums){
        singleNum ^= n;
    }
    return singleNum;
}

Complexity

1. Time complexity is O(n) by scanning the array once
2. Space complexity is O(1) without using additional data structrues