মান লিখুন: আমাদের কাছে N উপাদান বিশিষ্ট একটি অ্যারে A রয়েছে। আমাদের l এবং r-এর জোড়ার সংখ্যা বের করতে হবে যাতে A[l] XOR A[l+1] XOR ... 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 এর আকার
a, s, sx অ্যারে (আকার n+1)
for 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
for l := 1 থেকে n:
bg := l, en := n, r := l
যতক্ষণ bg <= en:
mid := (bg + en) / 2
যদি s[mid] - s[l-1] == (sx[mid] XOR sx[l-1]):
r := mid
bg := mid + 1
অন্যথায়:
en := mid - 1
res := res + (r - l + 1)
res রিটার্ন করুন
C++ বাস্তবায়ন
#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
