C++-এ সমান XOR ওয়ালা ট্রিপলেট গণনা

একটি ইন্টিজার অ্যারে arr দেওয়া আছে। তিনটি ইন্ডেক্স i, j, k (০ ≤ i < j ≤ k < N) বের করতে হবে যাতে a = arr[i] XOR ... XOR arr[j-1] এবং b = arr[j] XOR ... XOR arr[k] সমান হয়।

ইনপুট: [2,3,1,6,7] → আউটপুট: 4 (ট্রিপলেট: (0,1,2), (0,2,2), (2,3,4), (2,4,4))

সমাধানের ধাপগুলো:

প্রতি i = 1 থেকে n-1 পর্যন্ত:
- বাম পাশের সব সম্ভাব্য XOR x1 ম্যাপে কাউন্ট করব
- ডান পাশের সব সম্ভাব্য XOR x2 দিয়ে ম্যাপে মিল খুঁজব
- ret += m[x2]

উদাহরণ

নিচের কোডটি দেখুন −

#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}