Xin chào anh em tech warriors! Lại là Loser1 đây🌟
Hôm nay, chúng ta sẽ tiếp giải quyết một vấn đề thú vị thách thức khả năng hiểu biết của chúng ta về các phép toán bitwise—cụ thể là XOR. Hãy chuẩn bị để khám phá một bài toán yêu cầu tính toán phép XOR của tất cả các cặp giữa hai mảng. Nghe có vẻ thú vị phải không? Hãy cùng phân tích và giải quyết nó nhé!

Input: nums1 = [2,1,3], nums2 = [10,2,5,0]
Output: 13
Explanation:
A possible nums3 array is [8,0,7,2,11,3,4,1,9,1,6,3].
The bitwise XOR of all these numbers is 13, so we return 13.

Input: nums1 = [1,2], nums2 = [3,4]
Output: 0
Explanation:
All possible pairs of bitwise XORs are nums1[0] ^ nums2[0], nums1[0] ^ nums2[1], nums1[1] ^ nums2[0],
and nums1[1] ^ nums2[1].
Thus, one possible nums3 array is [2,5,1,6].
2 ^ 5 ^ 1 ^ 6 = 0, so we return 0.

First Impression & Intuition

Khi nhìn vào bài này lần đầu, có thể nhiều người sẽ nghĩ đến cách brute force - tạo ra tất cả các cặp có thể và XOR chúng lại. Nhưng với constraints cho thấy nums1 và nums2 có thể lên tới 10^5 phần tử, cách này sẽ dẫn đến Time Limit Exceeded. Chúng ta cần một cách tiếp cận thông minh hơn! 💡

Problem Breakdown

Hãy phân tích kỹ yêu cầu của bài toán:

1. Input:

• Hai mảng nums1 và nums2 chứa các số không âm
• Giới hạn: 1 ≤ nums1.length, nums2.length ≤ 10^5
• Các phần tử: 0 ≤ nums1[i], nums2[j] ≤ 10^9

1. Output:

• Kết quả XOR của tất cả các cặp số có thể tạo thành
• Mỗi số trong nums1 phải được ghép cặp với mọi số trong nums2

1. Challenges:

• Không thể tạo mảng phụ chứa tất cả các cặp (sẽ vượt quá bộ nhớ)
• Cần tìm ra quy luật để tránh việc XOR từng cặp một

Smart Approach

1. Phân Tích Chi Tiết

Hãy lấy một ví dụ nhỏ để thấy pattern:

nums1 = [1,2]
nums2 = [3,4]

Liệt kê tất cả các cặp XOR:
(1⊕3), (1⊕4), (2⊕3), (2⊕4)

Phân tích kỹ hơn:
- Số 1 xuất hiện 2 lần (với 3 và 4)
- Số 2 xuất hiện 2 lần (với 3 và 4)
- Số 3 xuất hiện 2 lần (với 1 và 2)
- Số 4 xuất hiện 2 lần (với 1 và 2)

2. Key Observations

1. Tần suất xuất hiện:

• Mỗi số trong nums1 xuất hiện ĐÚNG length(nums2) lần
• Mỗi số trong nums2 xuất hiện ĐÚNG length(nums1) lần

1. Tính chất quan trọng của XOR:

• a⊕a = 0 (một số XOR với chính nó bằng 0)
• a⊕0 = a (XOR với 0 không thay đổi giá trị)
• (a⊕b)⊕(a⊕b) = 0 (số chẵn lần sẽ triệt tiêu)
• Tính chất kết hợp: (a⊕b)⊕c = a⊕(b⊕c)

1. Phát hiện then chốt:

• Nếu length(nums2) chẵn → mỗi số trong nums1 xuất hiện chẵn lần → triệt tiêu
• Nếu length(nums2) lẻ → mỗi số trong nums1 xuất hiện lẻ lần → giữ lại
• Tương tự cho nums2

3. Chiến Lược Giải Quyết

1. Kiểm tra độ dài:

   if (size1 % 2 == 1) {  // nums1 có độ dài lẻ
       → mỗi số trong nums2 sẽ xuất hiện lẻ lần
       → cần XOR tất cả các số trong nums2
   }
   if (size2 % 2 == 1) {  // nums2 có độ dài lẻ
       → mỗi số trong nums1 sẽ xuất hiện lẻ lần
       → cần XOR tất cả các số trong nums1
   }

2. Xử lý các trường hợp:

• Cả hai mảng độ dài chẵn → kết quả = 0
• Một mảng lẻ một mảng chẵn → XOR tất cả phần tử của mảng còn lại
• Cả hai mảng độ dài lẻ → XOR tất cả phần tử của cả hai mảng

Code Implementation

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        int size1 = nums1.size();
        int size2 = nums2.size();
        int ans1 = 0, ans2 = 0;

        // Xử lý khi nums1 có size lẻ
        if (size1 % 2 == 1) {
            for (int num : nums2) ans2 ^= num;
        }

        // Xử lý khi nums2 có size lẻ
        if (size2 % 2 == 1) {
            for (int num : nums1) ans1 ^= num;
        }

        return ans1 ^ ans2;
    }
};

Test Cases & Visualization

// Test Case 1:
Input: nums1 = [2,1], nums2 = [3,4]
Output: 0
Giải thích: (2⊕3)⊕(2⊕4)⊕(1⊕3)⊕(1⊕4) = 0

// Test Case 2:
Input: nums1 = [1,2,3], nums2 = [6,5]
Output: 6⊕5 = 3
Giải thích: Size nums1 lẻ -> XOR all nums2

Complexity Analysis

• Time Complexity: O(n + m) - một lần duyệt qua mỗi mảng
• Space Complexity: O(1) - chỉ dùng biến đếm

Pro Tips & Tricks

1. Với bài XOR, luôn nghĩ đến tính chất đặc biệt của nó
2. Vẽ ra giấy để thấy pattern của các cặp số
3. Edge cases với mảng rỗng hay size = 1 rất quan trọng

Đó! Một bài toán tưởng phức tạp lại có solution cực kỳ elegant phải không anh em? 🚀

P/S: Nếu thích những bài phân tích kiểu này, đừng quên follow mình để đón những bài tiếp theo nhé! Happy coding! 💻✨

Code Editor