[LeetCode] 2425. Bitwise XOR of All Pairings

https://leetcode.com/problems/bitwise-xor-of-all-pairings/description/

leetcode - Bitwise XOR of All Pairings

문제 유형: 비트마스킹

문제 난이도: Medium

 

문제

You are given two 0-indexed arrays, nums1 and nums2, consisting of non-negative integers. There exists another array, nums3, which contains the bitwise XOR of all pairings of integers between nums1 and nums2 (every integer in nums1 is paired with every integer in nums2 exactly once).

Return the bitwise XOR of all integers in nums3.

 

0-indexed배열 nums1과 nums2를 받습니다. 요소들은 모두 자연수입니다.

다른 배열 nums3이 있습니다. 이것은 nums1과 nums2의 모든 XOR조합으로 구성됩니다.

 

nums3의 모든 요소들을 XOR한 값을 반환하시오.

 

풀이

당연히, 브루트 포스는 TLE에 걸린다.

문제를 간소화할 필요가 있다.

 

nums3을 모두 xor한 값을 생각해보자. n을 nums1의 크기, m을 nums2의 크기라 하자.

0에다가 (0 xor a는 a이므로, 0에 xor을 붙인다고 생각하면 편하다)

nums1[0]이 m번 XOR되고,

nums1[1]이 m번 XOR되고,

...

nums1[n-1]이 m번 XOR되고,

nums2[0]이 n번 XOR되고,

nums2[1]이 n번 XOR되고,

...

nums2[m-1]이 n번 XOR된다.

 

즉, n과 m의 홀짝여부가 중요하다.

m이 홀수라면 nums1의 수들을 한 번 XOR시키고,

n이 홀수라면 nums2의 수들을 한 번XOR시킨다.

 

 

코드

C++

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int m = nums2.size();

        int ans = 0;
        if(m%2 == 1) {
            for(int i = 0; i < n; ++i) {
                ans ^= nums1[i]; 
            }
        }

        if(n%2 == 1) {
            for(int i = 0; i < m; ++i) {
                ans ^= nums2[i];
            }
        }

        return ans;
    }
};