ধরুন আমাদের একটি অ্যারে আছে পূর্ণসংখ্যার arr। আমরা i, j এবং k এর মত তিনটি সূচক নির্বাচন করতে চাই যেখানে (0 <=i
সুতরাং, যদি ইনপুটটি [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
-
একটি মানচিত্র m
সংজ্ঞায়িত করুন -
x1 :=0, x2 :=0
-
j আরম্ভ করার জন্য :=i - 1, যখন j>=0, আপডেট করুন (j 1 দ্বারা কমিয়ে দিন), করুন −
-
x1 :=x1 XOR arr[j]
-
(m[x1] 1 দ্বারা বাড়ান)
-
-
j শুরু করার জন্য :=i, যখন j
করুন -
x2 :=x2 XOR arr[j]
-
ret :=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; 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