2425. Bitwise XOR of All Pairings

문제 링크


내 코드

XOR 규칙

0ms, 64.38MB

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

        int x1{}, x2{};
        if(m & 1) {
            x1 = allXor(nums1);
        }
        if(n & 1) {
            x2 = allXor(nums2);
        }

        return x1 ^ x2;
    }
    int allXor(vector<int>& nums) {
        int ret{};
        for(int num : nums) ret ^= num;
        return ret;
    }
};

Solution

Approach 1: Hash Map

  • 73ms, 93.15MB
  • Complexity
    • Let nn and mm be the lengths of the arrays nums1 and nums2 respectively.
    • Time Complexity: O(n+m)O(n + m)
    • Space Complexity: O(n+m)O(n + m)
class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        // Get lengths of arrays
        int len1 = nums1.size();
        int len2 = nums2.size();

        // Map to store frequency of each number
        unordered_map<int, long> freq;

        // Add frequencies for nums1 elements
        // Each element appears len2 times in final result
        for (int num : nums1) {
            freq[num] += len2;
        }

        // Add frequencies for nums2 elements
        // Each element appears len1 times in final result
        for (int num : nums2) {
            freq[num] += len1;
        }

        // XOR numbers that appear odd number of times
        int ans = 0;
        for (auto& [num, count] : freq) {
            if (count % 2 == 1) {
                ans ^= num;
            }
        }

        return ans;
    }
};

GPT (o3-mini-high)

이 코드는 두 배열 nums1과 nums2가 주어졌을 때,
각 배열의 원소들이 최종 XOR 연산에 몇 번씩 기여하는지를 이용하여 전체 XOR 값을 계산하는 솔루션입니다.
문제의 핵심 아이디어는 XOR 연산의 성질을 이용하는 것으로,
어떤 수가 짝수 번 XOR 연산에 참여하면 0이 되고, 홀수 번 참여하면 그 수 자체가 결과에 남는다는 점을 활용합니다.

아래 단계별로 코드를 자세히 설명하겠습니다.

1. 배열 길이와 빈도수를 저장할 맵 초기화

int len1 = nums1.size();
int len2 = nums2.size();

// 각 숫자가 최종 XOR 연산에서 몇 번 등장하는지를 기록하기 위한 맵
unordered_map<int, long> freq;
  • len1과 len2는 각각 배열 nums1과 nums2의 길이입니다.
  • 최종 연산에서 nums1의 각 원소는 nums2의 모든 원소와 결합되므로 len2번 등장합니다.
  • 반대로, nums2의 각 원소는 nums1의 모든 원소와 결합되므로 len1번 등장합니다.
  • 이를 이용해 각 숫자가 몇 번 XOR 연산에 기여하는지 계산할 때,
    바로 빈도수를 freq 맵에 저장합니다.

2. 각 배열의 원소별 등장 횟수 기록

// nums1의 각 원소는 최종 결과에 len2번 등장합니다.
for (int num : nums1) {
    freq[num] += len2;
}

// nums2의 각 원소는 최종 결과에 len1번 등장합니다.
for (int num : nums2) {
    freq[num] += len1;
}
  • nums1의 각 원소에 대해, 해당 숫자가 최종 XOR 연산에 len2번 등장하도록 freq[num]에 len2를 더합니다.
  • nums2의 각 원소에 대해서는 len1을 더합니다.
  • 이 과정에서 각 숫자가 최종 결과에 몇 번 등장하는지 누적되어 기록됩니다.

3. 홀수 번 등장하는 숫자들의 XOR 연산

int ans = 0;
for (auto& [num, count] : freq) {
    if (count % 2 == 1) {
        ans ^= num;
    }
}
  • XOR의 성질에 따르면, 같은 수가 짝수 번 XOR 연산에 참여하면 0이 되고, 홀수 번 참여하면 그 수가 결과에 남습니다.
  • 따라서, freq 맵을 순회하면서 각 숫자의 등장 횟수 count가 홀수인 경우에만
    최종 결과 ans에 해당 숫자를 XOR 연산으로 포함시킵니다.

4. 최종 결과 반환

return ans;
  • 모든 숫자에 대해 홀수 번 등장하는 숫자들을 XOR한 값이 최종 결과로 반환됩니다.

결론

  • 핵심 아이디어:
    • nums1의 각 원소는 nums2의 길이만큼, nums2의 각 원소는 nums1의 길이만큼 최종 XOR에 기여한다.
    • XOR 연산에서, 짝수 번 등장하는 숫자는 0으로 상쇄되고, 홀수 번 등장하는 숫자만 결과에 영향을 미친다.
  • 구현 방식:
    두 배열에 대해 각 숫자의 등장 횟수를 기록한 후,
    등장 횟수가 홀수인 숫자들에 대해 XOR 연산을 수행합니다.

이러한 방법으로, 전체 배열의 조합에서 발생하는 XOR 결과를 효율적으로 계산할 수 있습니다.


Approach 2: Space Optimized Bit Manipulation

  • 0ms, 64.10MB
  • Complexity
    • Let nn and mm be the lengths of the arrays nums1 and nums2 respectively.
    • Time Complexity: O(n+m)O(n + m)
    • Space Complexity: O(1)O(1)
class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        // Initialize XOR results for both arrays
        int xor1 = 0;
        int xor2 = 0;

        // Get lengths of both arrays
        int len1 = nums1.size();
        int len2 = nums2.size();

        // If nums2 length is odd, each element in nums1 appears odd times in
        // final result
        if (len2 % 2 != 0) {
            for (int num : nums1) {
                xor1 ^= num;
            }
        }

        // If nums1 length is odd, each element in nums2 appears odd times in
        // final result
        if (len1 % 2 != 0) {
            for (int num : nums2) {
                xor2 ^= num;
            }
        }

        // Return XOR of both results
        return xor1 ^ xor2;
    }
};

GPT (o3-mini-high)

이 코드는 두 배열 nums1과 nums2가 주어졌을 때,
모든 조합의 XOR 결과를 한 번에 계산하는 문제를 비트 연산의 성질을 이용하여 효율적으로 풀어줍니다.

문제의 핵심 아이디어는 다음과 같습니다.

  • 최종 결과는 두 배열의 원소들이 각각 몇 번씩 XOR 연산에 기여하는지에 따라 결정됩니다.
  • 배열 nums1의 각 원소는 nums2의 모든 원소와 조합되므로 최종 결과에 len2번 등장합니다.
  • 배열 nums2의 각 원소는 nums1의 모든 원소와 조합되므로 최종 결과에 len1번 등장합니다.
  • XOR 연산의 성질에 따라, 어떤 수가 짝수 번 등장하면 서로 상쇄되어 0이 되고, 홀수 번 등장하면 그 수가 결과에 남게 됩니다.

즉,

  • nums1의 각 원소가 최종 XOR 결과에 기여하는 횟수는 len2번입니다.
    → len2가 홀수라면, nums1의 원소들은 결과에 남고,
    → len2가 짝수라면 모두 상쇄되어 0 효과를 냅니다.
  • nums2의 각 원소도 마찬가지로, len1가 홀수일 때 결과에 기여합니다.

코드의 흐름을 단계별로 살펴보면 다음과 같습니다.

1. 초기화

int xor1 = 0;
int xor2 = 0;

int len1 = nums1.size();
int len2 = nums2.size();
  • xor1와 xor2는 각각 nums1과 nums2의 원소들을 XOR한 값을 저장할 변수입니다.
  • len1과 len2는 각각 배열의 길이를 저장합니다.

2. nums1의 기여 계산

if (len2 % 2 != 0) {
    for (int num : nums1) {
        xor1 ^= num;
    }
}
  • nums1의 각 원소는 최종 결과에 len2번 등장합니다.
  • 만약 len2가 홀수이면, 각 원소가 홀수 번 등장하여 XOR 결과에 영향을 줍니다.
    → 이 경우 nums1의 모든 원소를 XOR하여 xor1에 저장합니다.
  • 반면 len2가 짝수이면, 각 원소가 짝수 번 등장하여 서로 상쇄되므로 아무런 기여도 하지 않습니다.

3. nums2의 기여 계산

if (len1 % 2 != 0) {
    for (int num : nums2) {
        xor2 ^= num;
    }
}
  • nums2의 각 원소는 최종 결과에 len1번 등장합니다.
  • 만약 len1이 홀수이면, nums2의 원소들이 결과에 기여하므로, XOR한 값을 xor2에 저장합니다.
  • len1이 짝수이면, 기여하지 않습니다.

4. 최종 결과 계산

return xor1 ^ xor2;
  • 최종 결과는 xor1과 xor2를 XOR한 값입니다.
  • 즉, 두 배열에서 홀수 번 등장하는 원소들의 XOR 값을 결합한 것이 최종 결과가 됩니다.

결론

이 코드는 두 배열의 길이의 홀짝 여부를 이용해,

  • nums1의 원소가 nums2의 길이가 홀수일 때만 XOR에 기여하고,
  • nums2의 원소가 nums1의 길이가 홀수일 때만 XOR에 기여하도록 하여
    전체 조합의 XOR 값을 효율적으로 계산합니다.

이러한 방식은 모든 조합을 직접 계산하지 않고,
XOR의 교환법칙과 상쇄 성질을 활용하여 O(n + m) 시간에 문제를 해결할 수 있습니다.