[Python] 2425. Bitwise XOR of All Pairings

난이도 : Medium

 

양수로만 구성된 num1와 num2라는 배열이 있는데, 두 배열의 요소들을 하나씩 XOR 취한 것을 num3로 취한다.

이 num3의 요소를 또, 전부 XOR 취한 값을 계산하는 문제

 

from functools import reduce
class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        ans = [x ^ y for x in nums1 for y in nums2]
        return reduce(lambda x, y : x ^ y, ans)

이렇게 정석적으로 풀었더니, Memory limit에 걸렸다.. 하하

 

 

이 문제를 풀기 위해서는 먼저 XOR의 특성이 중요한데, XOR는 다음과 같이 계산된다.

출처 : Leetcode

 

위 문제에서는 nums1의 숫자 갯수가 a, nums2의 숫자 갯수가 b라고 할 때

nums1의 요소는 b번, nums2의 요소는 a번 XOR 계산을 진행한다고 할 수 있다. 

또한, XOR 계산을 2번 반복하면 0이 된다는 점이 제일 중요하다.

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        a, b = len(nums1), len(nums2)
        xor1, xor2 = 0, 0
        
        if a % 2 != 0:
            for i in nums2:
                xor2 ^= i
        
        if b % 2 != 0:
            for i in nums1:
                xor1 ^= i
        
        return xor1 ^ xor2

그래서 a가 홀수일 때, nums2의 XOR 계산을 진행하고

b가 홀수일 때, nums1의 계산을 진행한 후, 양쪽을 XOR 진행하였다.

 

Runtime : 4ms (60.50%)

Memory : 36.70MB (13.77%)