मान लीजिए हमारे पास N तत्वों वाला एक ऐरे A है। हमें पूर्णांकों l और r के उन युग्मों की संख्या ढूंढनी है जो संतुष्ट करते हैं A[l] XOR A[l+1] XOR ... XOR A[r-1] XOR A[r] = A[l] + A[l+1] + ... A[r]।
उदाहरण के लिए, यदि इनपुट A = [2, 5, 4, 6] है, तो आउटपुट 5 होगा, क्योंकि युग्म (1,1), (2,2), (3,3), (4,4) और (1,2) के लिए।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := A का आकार आकार (n + 1) के कुछ ऐरे a, s और sx परिभाषित करें i := 1 से n तक, करें: a[i] := A[i - 1] s[i] := s[i - 1] + a[i] sx[i] := sx[i - 1] XOR a[i] res := 0 l := 1 से n तक, करें: bg := l, en = n, r = l जब तक bg <= en, करें: mi := (bg + en) / 2 यदि s[mi] - s[l - 1], (sx[mi] XOR sx[l - 1]) के बराबर है, तो: r := mi bg := mi + 1 अन्यथा en := mi - 1 res := res + (r - l + 1) res वापस करें
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; int solve(vector<int> A){ int n = A.size(); vector<int> a(n + 1), s(n + 1), sx(n + 1); for (int i = 1; i <= n; i++){ a[i] = A[i - 1]; s[i] = s[i - 1] + a[i]; sx[i] = sx[i - 1] ^ a[i]; } int res = 0; for (int l = 1; l <= n; l++){ int bg = l, en = n, r = l; while (bg <= en){ int mi = (bg + en) / 2; if (s[mi] - s[l - 1] == (sx[mi] ^ sx[l - 1])){ r = mi; bg = mi + 1; } else en = mi - 1; } res += (r - l + 1); } return res; } int main(){ vector<int> A = { 2, 5, 4, 6 }; cout << solve(A) << endl; } इनपुट
{ 2, 5, 4, 6 } आउटपुट
5