मान लीजिए हमारे पास इंटीजर्स का एक ऐरे arr है। हम i, j और k जैसे तीन इंडेक्स चुनना चाहते हैं जहां (0 <= i < j <= k < N), N ऐरे का आकार है। a और b के मान निम्न हैं: a = arr[i] XOR arr[i + 1] XOR ... XOR arr[j - 1] b = arr[j] XOR arr[j + 1] XOR ... XOR arr[k] हमें ट्रिपलेट (i, j, k) की संख्या ढूंढनी है जहां a, b के समान है।
इसलिए, यदि इनपुट है [2,3,1,6,7], तो आउटपुट 4 होगा, क्योंकि ट्रिपलेट हैं (0,1,2), (0,2,2), (2,3,4) और (2,4,4)
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
ret := 0
n := arr का आकार
i := 1 से शुरू करें, जब i < n, i बढ़ाते हुए, करें -
एक मैप m परिभाषित करें
x1 := 0, x2 := 0
j := i - 1 से शुरू करें, जब j >= 0, j घटाते हुए, करें -
x1 := x1 XOR arr[j]
(m[x1] को 1 से बढ़ाएं)
j := i से शुरू करें, जब j < n, j बढ़ाते हुए, करें -
x2 := x2 XOR arr[j]
ret := ret + m[x2]
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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; int 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; } }; main(){ Solution ob; vector<int> v = {2,3,1,6,7}; cout << (ob.countTriplets(v)); }इनपुट
{2,3,1,6,7}आउटपुट
4
