LeetCode [136] Single Number

136. Single Number

Easy

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 1:

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

Example 2:

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

Output: 4 

Note:

• 1 xor 1=0
• 0 xor 1=1
• eg. 101, 101 and 110
• 101 xor 101 = 000
• 000 xor 110 = 110

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

//C++: 20ms class Solution { public: int singleNumber(vector<int>& nums) { return accumulate(nums.begin(), nums.end(), 0, bit_xor<int>()); } }; //Java class Solution { public int singleNumber(int[] nums) { int ret = 0; for (int i : nums) { ret = ret^i; } return ret; } }