LeetCode 136. 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:

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

Output: 4

 

-Summary-

Using XOR Bit operation

1. Do XOR bit operation for all numbers

2. return the answer 

https://www.khanacademy.org/computing/computer-science/cryptography/ciphers/a/xor-bitwise-operation

EX) [4,1,2,1,2]

1 XOR 1 XOR 2 XOR 2 = 0

0 XOR 4 = 4

 

처음엔 defaultdict 를 새로 만들어서 approach 하였는데, 답을 보니 bit operation으로 extra memory 없이 가능한 방법이 있었다. 오늘도 공부하면서 배운다.

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]