ধরুন আমাদের কাছে N উপাদান সহ একটি অ্যারে রয়েছে। আমাদের A[l] XOR A[l+1] XOR... XOR A[r-1] XOR A[r] =A[l] + A[কে পূর্ণ করে l এবং r-এর জোড়া সংখ্যা খুঁজে বের করতে হবে। l+1] + ... A[r]।
সুতরাং, যদি ইনপুটটি A =[2, 5, 4, 6] এর মত হয়, তাহলে আউটপুট হবে 5, কারণ জোড়ার জন্য (1,1), (2,2), (3,3), (4, 4) এবং (1,2)।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
n := size of A Define some arrays of size (n + 1) each, a, s and sx for initialize i := 1, when i <= n, update (increase i by 1), do: a[i] := A[i - 1] s[i] := s[i - 1] + a[i] sx[i] := sx[i - 1] XOR a[i] res := 0 for initialize l := 1, when l <= n, update (increase l by 1), do: bg := l, en = n, r = l while bg <= en, do: mi := (bg + en) / 2 if s[mi] - s[l - 1] is same as (sx[mi] XOR sx[l - 1]), then: r := mi bg := mi + 1 Otherwise en := mi - 1 res := res + (r - l + 1) return 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
