XOR ของ XOR ทุก subarray ใน C++

โจทย์

ได้รับอาร์เรย์ขนาด n ต้องการหา XOR ของ XOR ทุก subarray ที่เป็นไปได้ (นำไปตามลำดับ)

ตัวอย่าง

Input: array = {1, 3, 6, 8}
Output: 0

คำอธิบาย

(1) ^ (3) ^ (6) ^ (8) ^ (1^3) ^ (3^6) ^ (6^8) ^ (1^3^6) ^ (3^6^8) ^ (1^3^6^8)

วิธีแก้ปัญหาที่มีประสิทธิภาพ

แทนที่จะหา subarray ทุกตัว (O(n²)) ใช้คุณสมบัติของ XOR:

XOR ของตัวเลขเดียวกันจำนวนคู่ครั้ง = 0
นับความถี่ (frequency) ของแต่ละองค์ประกอบที่ปรากฏในทุก subarray
เฉพาะองค์ประกอบที่มีความถี่เป็น จำนวนคี่ (odd) เท่านั้นที่ส่งผลต่อผลลัพธ์สุดท้าย

สูตรหาความถี่ขององค์ประกอบที่ index i (0-based) ในอาร์เรย์ขนาด N:

frequency = (i + 1) * (N - i)

เหตุผล: องค์ประกอบที่ index i จะอยู่ใน subarray ที่เริ่มต้นที่ 0 ถึง i (รวม i+1 ทางเลือก) และจบที่ i ถึง N-1 (รวม N-i ทางเลือก)

โค้ดตัวอย่าง

#include <iostream>
using namespace std;

int xorSubarrayXors(int arr[], int N) {
    int result = 0;
    for (int i = 0; i < N; i++) {
        long long frequency = 1LL * (i + 1) * (N - i);  // ใช้ long long ป้องกัน overflow
        if (frequency % 2 == 1) {
            result ^= arr[i];
        }
    }
    return result;
}

int main() {
    int arr[] = {1, 3, 6, 8};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "The xor of all subarray xors is: " << xorSubarrayXors(arr, N);
    return 0;
}

ผลลัพธ์

The xor of all subarray xors is: 0

ข้อสังเกตเพิ่มเติม

สูตร (i+1)*(N-i) ให้ความถี่ที่แน่นอน
ต้องใช้ long long สำหรับ frequency เพื่อป้องกัน overflow เมื่อ N ใหญ่
Time complexity: O(N) - เร็วมากกว่าวิธี brute force O(N²) หรือ O(N³) มาก
Space complexity: O(1) - ใช้พื้นที่คงที่

สรุป

โจทย์ที่ดูซับซ้อน O(N²) สามารถลดเป็น O(N) ได้ด้วยการวิเคราะห์คุณสมบัติของ XOR และความถี่ของแต่ละองค์ประกอบใน subarray ทั้งหมด เป็นเทคนิคสำคัญใน competitive programming