[Leetcode] 136. Single Number

21-11-25
solved in another way

Problems

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.

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

Solution

from functools import reduce
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda acc,cur:acc^cur,nums)

기존 set 쓰던 풀이에서 bit manipulation으로 바꿨다. set 쓰면 공간 n 먹어서 위 풀이가 더 효율적이다.

위 풀이를 이해하려면 bit 연산의 성질을 알아야 한다.

XOR 연산
1) commutative law 성립: a^b=b^a
2) 0^a=a
3) a^a=0

따라서 위 예제에서 모든 연산을 xor로 처리하면 다음과 같다.

4^1^2^1^2
=4^1^1^2^2
=4^0^0 = 4^0 =4

모르면 맞아야지하는 문제 같다.

이를 베이스로 260. Single Number III도 풀어보자.