leetcode : Single Number

https://leetcode.com/problems/single-number/

Single Number - LeetCode

 

time complexity O(N)

space complexity O(1)으로 풀어야 되는 문제

 

처음엔 array를 스캔하면서 해당 array 공간을 활용해 정보를 저장할 생각을 해보았으나 불가능함을 깨달았다.

 

뭔가 풀이 방법이 안 떠올라서 이게 왜 Easy지? 왜? 대체!? 하고 생각하다가

Related Topics를 열었고 Bit Manipulation이라고 되어있는 걸 확인했다.

Bit Manipulation 문제가 있다는 걸 들어보기만 했지 실제로 푸는 건 처음이라

Python Bitwise Operators를 다시 찾아보던 중 문득 XOR 연산자를 보고 풀이 방법이 생각났다.

같은 숫자는 XOR하면 0으로 없어지고 이 연산자가 교환법칙 ,결합법칙 등이 성립되어 연산 순서가 상관이 없다면 모든 리스트의 숫자를 XOR했을 때 Single Number만 남겠구나..!

 

from functools import reduce

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x,y:x^y, nums, 0)