###### tags: `Leetcode` `easy` `bit` `python` `c++` `Top 100 Liked Questions`

# 136. Single Number

## [題目出處:] https://leetcode.com/problems/single-number/

## 題目:
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a **linear runtime complexity** and **use only constant extra space.**

## 解題思考:
使用XOR ^

| Expression1 | Expression2 | Result |
|:-----------:|:-----------:|:------:|
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
| 1 | 1 | 0 |

自己^自己=0
任何數^0=任何數自己

## Python:

#linear runtime complexity
#use only constant extra space.
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #此方法對 但有用到額外array 🤡
        '''
        ans = []
        for i in range(len(nums)):
            if ans.__contains__(nums[i]):
                ans.remove(nums[i])
            else:
                ans.append(nums[i])
        return ans[0]
        '''
        #正解: 用XOR -> a^b
        res=0
        for val in nums:
            res^=val
        return res

if __name__ == '__main__':
    result = Solution()
    nums = [4,1,2,1,2]
    ans = result.singleNumber(nums)
    print(ans)

## C++:

#include<iostream>
#include<vector>
using namespace std;

class Solution{
public:
    int singleNumber(vector<int>& nums){
        int ans=0;
        for (int val:nums){
            ans^=val;
        }
        return ans;
    }
};

int main(){
    vector<int> nums={4,1,2,1,2};
    Solution res;
    int ans=res.singleNumber(nums);
    cout<<ans<<endl;
    return 0;
}