Single Number

Question

Given a non-empty 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?

Example:

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

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

Analyzation

Bit Calculation XOR

Take 12 and 7 as an example:

12 : 0000 1100 7 : 0000 0111

12 XOR 7 : 0000 1011 = 11 11 XOR 12: 0000 0111 = 7

So, 12 XOR 7 XOR 12 = 7 which is the single number.

The Code

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

        return nums[0];
    }
}

Time & Space Complexity

• Time Complexity: O(n). Only scanning.
• Space Complexity: O(1). No extra data structure is used.