# Single Number Problem

0 like 0 dislike
605 views

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```

0 like 0 dislike
by Goeduhub's Expert (2.3k points)

Concept

If we take XOR of zero and some bit, it will return that bit

a⊕0=a

If we take XOR of two same bits, it will return 0

a⊕a=0

a⊕b⊕a=(a⊕a)⊕b=0⊕b=b

So we can XOR all bits together to find the unique number.

class Solution(object):

def singleNumber(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

a = 0

for i in nums:

a ^= i

return a

eg : ans = Solution()

ans.singleNumber([2,2,1])

Output -

1

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.