นับ Triplets ที่สร้างอาร์เรย์ XOR เท่ากันได้ใน C++

สมมติว่าเรามีอาร์เรย์จำนวนเต็ม arr เลือก i, j, k โดย 0 ≤ i < j ≤ k < N ให้ a = arr[i] XOR ... XOR arr[j-1], b = arr[j] XOR ... XOR arr[k] หาจำนวน triplets ที่ a == b

ตัวอย่าง: [2,3,1,6,7] ผลลัพธ์ = 4 triplets: (0,1,2), (0,2,2), (2,3,4), (2,4,4)

วิธีแก้ปัญหา

สังเกต: a == b ⟺ XOR จาก i ถึง k = 0
สำหรับแต่ละจุดกึ่งกลาง j:
- คำนวณ prefix XOR ย้อนกลับจาก j-1 เก็บ frequency ใน map
- คำนวณ prefix XOR ไปข้างหน้าจาก j หา frequency ที่ตรงกัน
รวมจำนวนคู่ที่ตรงกัน

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

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int countTriplets(vector<int>& arr) { 
        int ret = 0; 
        int n = arr.size(); 
        for (int i = 1; i < n; i++) { 
            map<int, int> m; 
            int x1 = 0, x2 = 0; 
            for (int j = i - 1; j >= 0; j--) { 
                x1 = x1 ^ arr[j]; 
                m[x1]++; 
            } 
            for (int j = i; j < n; j++) { 
                x2 = x2 ^ arr[j]; 
                ret += m[x2]; 
            } 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {2,3,1,6,7}; 
    cout << (ob.countTriplets(v)); 
}

ข้อมูลนำเข้า

{2,3,1,6,7}