LC136 - Single Number

Problem

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.

Example

Input: nums = [2,2,1]

Output: 1

Solution

Intuition

Push elements to stack and pop when it's duplicate is found. Problem with this solution is that it does not use constant space.

Bitwise

Bitwise XOR of two of the same number is always zero, so the remaining number after doing bitwise XOR on every element in the list is the single remaining number.

def singleNumber(self, nums: List[int]) -> int:
	res = 0
	for num in nums:
		res = res ^ num
	return res