Single Number

Posted on

Problem

Given an 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?

 Solution

Screen Shot 2016-08-31 at 10.37.45 AM

Use a trick of bitwise operation XOR: 0^n = n . n is an integer. So here use zero to XOR each element. If there are even number of the element, result will be back to zero and ready to be XOR with the next element. If there are odd number of the element, result will be the element itself. Furthermore, XOR is commutative. So the order in the array doesn’t matter.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s