C++ में समान XOR के दो सरणियों का निर्माण कर सकने वाले त्रिकों की गणना करें

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है। हम तीन सूचकांकों जैसे i, j और k का चयन करना चाहते हैं जहां (0 <=i

इसलिए, यदि इनपुट [2,3,1,6,7] जैसा है, तो आउटपुट 4 होगा, क्योंकि त्रिक हैं (0,1,2), (0,2,2), (2,3 ,4) और (2,4,4)

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• रिट:=0

• n :=गिरफ्तारी का आकार

• इनिशियलाइज़ करने के लिए मैं :=1, जब i

  • एक नक्शा परिभाषित करें मी

  • x1:=0, x2:=0

  • इनिशियलाइज़ j :=i-1 के लिए, जब j>=0, अपडेट करें (j को 1 से घटाएं), −

    करें

    • X1 :=X1 XOR गिरफ्तारी[j]

    • (m[x1] 1 से बढ़ाएं)

  • इनिशियलाइज़ j :=i के लिए, जब j

    • x2 :=x2 XOR गिरफ्तारी[j]

    • रिट :=रिट + एम[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