https://leetcode.com/problems/bitwise-xor-of-all-pairings
xor의 특성에 대해 파악해 해결한 문제였습니다.
📕 풀이방법
📔 입력 및 초기화
다음 변수를 선언합니다.
📑 nums1의 xor을 저장할 xors1와 num2의 xor한 결과를 저장할 xors2를 선언해 각 배열들을 xor한 값을 각각 저장합니다.
📑 nums1, nums2의 길이 len1, len2를 선언 후 저장합니다.
📔 풀이과정
📑 10만이 배열 최대 길이이므로 O(n^2)로 풀 수 없습니다. xor의 특성을 이용해야 합니다. 예제로 살펴보겠습니다. 숫자들을 알파뱃으로 바꿔 표현하면 여러 경우에 대해 다음과 같이 표현할 수 있습니다.
1. nums1 = [a,b], nums2 = [c]인 경우
1-1. xor된 원소들은 : a^c, b^c이 되며 이들을 모두 xor한 경우 a^b^c^c가 됩니다.
1-2. 자기 자신을 xor하게 되면 0이되는 특성으로 a^b가 됩니다.
1-3. 이를 통해 nums1의 길이가 짝수라면 홀수인 nums2는 xor처리를 통해 모두 0이되므로 xors1을 반환하면 됩니다.
2. nums1 = [a], nums2 = [b,c]
2-1. xor된 원소들은 : a^b, a^c이 되며 이들을 모두 xor한 경우 a^b^c^c가 됩니다.
2-2. 자기 자신을 xor하게 되면 0이되는 특성으로 a^b가 됩니다.
2-3. 이를 통해 nums2의 길이가 짝수라면 경우 1과 비슷한 논리로 xors2를 반환하면 됩니다.
3. nums1 = [a,b], nums2 = [c,d]
3-1. xor된 원소들은 : a^c, a^d, b^c, b^d며 이들은 모두 xor한 경우 a^c^a^d^b^c^b^d가 되며 각자 원소가 자기 자신에 대해 두 번씩 계산되므로 모두 0이 되며 따라서 0을 반환하면 됩니다.
4. nums1 = [a], nums2 = [b]
4-1. 각 원소가 홀수번씩 계산되므로 xors1 ^ xors2를 반환하면 됩니다.
📕 Code
📔 Python3
class Solution:
def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
xors1, xors2 = 0, 0
for num in nums1:
xors1 ^= num
for num in nums2:
xors2 ^= num
len1, len2 = len(nums1), len(nums2)
if len1 % 2 == 0 and len2 % 2 == 0:
return 0
if len1 % 2 == 0:
return xors1
if len2 % 2 == 0:
return xors2
return xors1 ^ xors2*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.