136. Single Number

Level: Easy
Link: https://leetcode.com/problems/single-number/

Problem

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:

Example 2

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

Solution

• Approach 1: List operation
• Approach 2: Hash Table
• Approach 3: Math
• Approach 4: Bit Manipulation