C++ में XOR के साथ शून्य के रूप में उप-सरणी की संख्या को अधिकतम करें

हमें एक सरणी दी गई है Arr[] जिसमें पूर्णांक मान हैं। लक्ष्य XOR के साथ 0 के रूप में उपसरणियों की अधिकतम संख्या को खोजना है। किसी भी उपसरणी के बिट्स को कितनी भी बार स्वैप किया जा सकता है।

नोट:- 1<=Arr[i]<=10¹⁸

बिट्स को स्वैप करके किसी भी सबरे के XOR को 0 बनाने के लिए, दो शर्तों को पूरा करना होगा:-

यदि बाएं से दाएं की सीमा में सेट बिट्स की संख्या सम है।
बिट्स की किसी भी श्रेणी के योग के लिए <=2 (सेट बिट्स में सबसे बड़ी संख्या)

आइए इसके लिए विभिन्न इनपुट आउटपुट परिदृश्य देखें -

में −Arr[] ={ 1,2,5,4 }

बाहर -

केवल पहली शर्त को संतुष्ट करने वाली उप-सरणी:4

दोनों स्थितियों को संतुष्ट करने वाली उप-सरणी :3

में - अरे [] ={ 3,7,2,9 }

बाहर -

केवल पहली शर्त को संतुष्ट करने वाली उप-सरणी:6

दोनों स्थितियों को संतुष्ट करने वाली उप-सरणी :3

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है -

इस दृष्टिकोण में हमने देखा कि बिट्स को स्वैप करके किसी भी सबरे के एक्सओआर को 0 के रूप में बनाने के लिए, दो शर्तों को पूरा करना होगा:- यदि बाएं से दाएं सीमा में सेट बिट्स की संख्या सम है या किसी भी श्रेणी के बिट्स के योग के लिए <=2 (सेट बिट्स में सबसे बड़ी संख्या)

इनपुट सरणी Arr[] लें और इसकी लंबाई की गणना करें।
फ़ंक्शन निकालेंसुबार (int arr[], int len) उन सबएरे की गिनती देता है जो संतोषजनक स्थिति नहीं है 2.
प्रारंभिक गणना 0 के रूप में लें।
लूप के लिए उपयोग करके सरणी को पुनरावृत्त करें और चर योग और अधिकतम वैल लें।
60 उप-सरणी की सीमा में पुनरावृति के लिए लूप के लिए एक और लें क्योंकि 60 से अधिक की स्थिति 2 कभी भी झूठी नहीं हो सकती।
योग में तत्व जोड़ें और अधिकतम मान लें।
यदि योग सम है और 2 * maxVal> योग तो शर्त 2 पूरी नहीं होने पर वेतन वृद्धि की गणना।
दोनों लूपों के अंत में गिनती वापस आती है।
फ़ंक्शन findSubarrays(int arr1[], int len1) एक इनपुट सरणी और उसकी लंबाई लेता है और ऊपर उल्लिखित दोनों स्थितियों को संतुष्ट करने वाले सबएरे की गिनती देता है।
केवल शर्त 1 का पालन करने वाली उप-सरणी की गणना करने के लिए एक उपसर्ग सरणी लें।
लूप के लिए उपयोग करके ट्रैवर्स सरणी और प्रत्येक तत्व को __builtin_popcountll(arr1[i]) के साथ सेट करें जो इसमें सेट बिट्स की संख्या है।
लूप के लिए उपसर्ग सरणी को पॉप्युलेट करें और उपसर्ग सेट करें [i] =उपसर्ग [i] + उपसर्ग [i - 1] जहां पहले तत्व को छोड़कर।
उपसर्ग सरणी में विषम और सम मानों की गणना करें।
tmp1=(oddcount * (oddcount-1) )/2 और tmp2=(evencount * (evencount-1) )/2 और दोनों के योग के रूप में परिणाम सेट करें।
परिणाम केवल 1 शर्त को संतुष्ट करने वाली उप-सरणी का योग होगा।
प्रिंट परिणाम।
अब परिणाम के साथ परिणाम अपडेट करें =परिणाम - हटाएंसुबार (arr1, len1)।
अब परिणाम में दोनों स्थितियों को संतुष्ट करने वाले उप-सरणी शामिल हैं।
परिणाम फिर से प्रिंट करें।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
// Function to count subarrays not satisfying condition 2
int removeSubarr(int arr[], int len){
   int count = 0;
   for (int i = 0; i < len; i++){
      int sum = 0;
      int maxVal = 0;

      for (int j = i; j < min(len, i + 60); j++){
         sum = sum + arr[j];
         maxVal = arr[j] > maxVal ? arr[j]: maxVal;

         if (sum % 2 == 0){
            if( 2 * maxVal > sum)
               { count++; }
         }
      }
   }
   return count;
}
int findSubarrays(int arr1[], int len1){
   int prefix[len1];
   int oddcount, evencount;
   int result;
   for (int i = 0; i < len1; i++)
   { arr1[i] = __builtin_popcountll(arr1[i]); }

   for (int i = 0; i < len1; i++){
      prefix[i] = arr1[i];
      if (i != 0)
         { prefix[i] = prefix[i] + prefix[i - 1]; }
      }
      oddcount = evencount = 0;
      for (int i = 0; i < len1; i++){
         if (prefix[i] % 2 == 0)
            { evencount = evencount +1; }
         else
            { oddcount = oddcount +1; }

      }
      evencount++;
      int tmp1= ( oddcount * (oddcount-1) )/2;
      int tmp2= ( evencount * (evencount-1) )/2;
      result = tmp1+tmp2;
      cout << "Subarrays satisfying only 1st condition : "<<result << endl;
      cout << "Subarrays satisfying both condition : ";
      result = result - removeSubarr(arr1, len1);
      return result;
   }
   int main()
   { int Arr[] = { 1,2,5,4 };
   int length = sizeof(Arr) / sizeof(Arr[0]);
   cout << findSubarrays(Arr, length);
   return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउट उत्पन्न करेगा

Subarrays satisfying only 1st condition : 4
Subarrays satisfying both condition : 3