LeetCode #136 Single Number

Easy

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:

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

Solution — Hash Set Operations

Iterates entire nums list and add each number into set when it is met first time and remove it in second time. The last one remains will be the answer.

Complexity

Iterating entire list takes O(n) time if n denotes to counts of numbers in this list. Both add and remove operations take O(logn)/O(1) in worst/average cases. Therefore, time complexity is O(nlogn)/O(n) in worst/average cases.

For space complexity, it use O(n) extra space.

Solution — Hash Set Math

By using hash set, we can easily compact nums to be a list without duplicated numbers. Then we can utilize following formula to calculate the answer:

2 * (a + b + c) — (a + a + b + b + c) = c

Complexity

It takes O(n) time to build and sum up elements for a hash set if n denotes to counts of numbers in nums. It also takes O(n) time to sum up the original list. Therefore, it’s time complexity is O(n + n) = O(n).

It’s trivial that we use O(n) extra space for build a hash set.

Solution — Bit Operations

With XOR operation, the same number will be eliminated, so the rest one will be our answer.

Complexity

It’s trivial that it takes O(n) time and O(1) extra space in this approach if n denotes to counts of numbers in nums.