21-11-25
sovled with hint
Problem
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
Example 1:
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] is also a valid answer.
Solution
from functools import reduce
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
l=len(nums)
if l==2:
return nums
ans=[]
#get xor sum
xSum=reduce(lambda acc,cur:acc^cur,nums)
#find the rightmost different bit
cnt=0
tSum=xSum
while not tSum&1:
tSum>>=1
cnt+=1
grainer= 1<<cnt
num1=0
for num in nums:
if num&grainer:
num1^=num
return [num1,num1^xSum]힌트 없었으면 못 풀었을 것 같다. 그런데 로직이 너무 재미있다.
- Single Number에서 다뤘던 XOR 연산자 성질을 다시 언급하면 다음과 같다.
a^b = b^a
a^0=a
a^a=0 ...(*)
여기서 (*)이 가장 중요하다.
우선 136번과 같이 xorSum을 구해준다. 그러면 찾고자하는 숫자 num1,num2의 xor만 남게 된다.
여기서 문제는 num1^num2에서 num1만 어떻게 끄집어 낼까이다.
num1^num2에서 i번째 비트가 1이라면 num1과 num2의 i번째 비트가 다르다는 것을 의미한다. 그럼 array의 모든 elems 중에서 i번째 비트가 1인 것들만 xor 연산을 하면 num1(또는 num2)를 포함해서 쌍으로 이루어진 숫자들로 xor sum이 만들어질 것이다. 이 때, 쌍으로 이루어진 숫자는 소거되므로 xor sum은 num1과 같다. num2는 전체 xSum에서 xor하면 쉽게 구할 수 있다.
c.f) (*)에서 a를 숫자 하나가 아니라 비트하나라고 볼 수 있다.
따라서 xorSum에서 i번째 비트가 1이면 array에서 i번째 비트가 1인 elem이 홀수 개 있다고 볼 수 있다.
bit manipulation 쪽에 새롭고 재밌는 것들이 많은 것 같다.
