हमें एक सरणी Arr[] दी गई है जिसमें पूर्णांक मान हैं। लक्ष्य XOR को 0 बनाने वाले उपसरणियों की अधिकतम संख्या ढूंढना है। किसी भी उपसरणी के बिट्स को किसी भी संख्या में स्वैप किया जा सकता है।
नोट: 1 <= Arr[i] <= 10^18
किसी भी उपसरणी के XOR को बिट्स स्वैप करके 0 बनाने के लिए, दो शर्तों को पूरा करना होगा:
- यदि रेंज लेफ्ट से राइट में सेट बिट्स की संख्या सम है।
- किसी भी दी गई रेंज के लिए बिट्स का योग <= 2 (सेट बिट्स में सबसे बड़ी संख्या)।
विभिन्न इनपुट-आउटपुट परिदृश्य देखते हैं:
इनपुट: Arr[] = { 1, 2, 5, 4 }
आउटपुट:
केवल पहली शर्त पूरी करने वाली उपसरणियाँ: 4
दोनों शर्तें पूरी करने वाली उपसरणियाँ: 3
इनपुट: Arr[] = { 3, 7, 2, 9 }
आउटपुट:
केवल पहली शर्त पूरी करने वाली उपसरणियाँ: 6
दोनों शर्तें पूरी करने वाली उपसरणियाँ: 3
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण:
इस दृष्टिकोण में हमने देखा कि किसी भी उपसरणी के XOR को बिट्स स्वैप करके 0 बनाने के लिए, दो शर्तों को पूरा करना होगा: यदि रेंज लेफ्ट से राइट में सेट बिट्स की संख्या सम है या किसी भी दी गई रेंज के लिए बिट्स का योग <= 2 (सेट बिट्स में सबसे बड़ी संख्या)।
- इनपुट सरणी Arr[] लें और इसकी लंबाई गणना करें।
- फंक्शन removeSubarr(int arr[], int len) शर्त 2 को पूरा न करने वाली उपसरणियों की संख्या लौटाता है।
- प्रारंभिक काउंट को 0 के रूप में लें।
- फॉर लूप का उपयोग करके सरणी पर पुनरावृति करें और sum और maxVal वेरिएबल्स लें।
- 60 उपसरणियों की रेंज में पुनरावृति करने के लिए एक और फॉर लूप लें क्योंकि 60 से आगे शर्त 2 कभी गलत नहीं हो सकती।
- तत्व को sum में जोड़ें और maxVal में अधिकतम लें।
- यदि sum सम है और 2 * maxVal > sum तो काउंट बढ़ाएं क्योंकि शर्त 2 पूरी नहीं होती।
- दोनों लूप के अंत में काउंट लौटाएं।
- फंक्शन findSubarrays(int arr1[], int len1) एक इनपुट सरणी और इसकी लंबाई लेता है और उपरोक्त दोनों शर्तों को पूरा करने वाली उपसरणियों की संख्या लौटाता है।
- पहली शर्त का पालन करने वाली उपसरणियों की संख्या गणना करने के लिए एक प्रीफिक्स सरणी लें।
- फॉर लूप का उपयोग करके सरणी को ट्रैवर्स करें और प्रत्येक तत्व को __builtin_popcountll(arr1[i]) पर सेट करें जो इसमें सेट बिट्स की संख्या है।
- फॉर लूप का उपयोग करके प्रीफिक्स सरणी को भरें और prefix[i] = prefix[i] + prefix[i - 1] सेट करें जहां पहला तत्व छोड़कर।
- प्रीफिक्स सरणी में विषम और सम मानों की गणना करें।
- tmp1 = (oddcount * (oddcount-1))/2 और tmp2 = (evencount * (evencount-1))/2 सेट करें और परिणाम दोनों के योग के रूप में।
- परिणाम केवल पहली शर्त को पूरा करने वाली उपसरणियों का योग होगा।
- परिणाम प्रिंट करें।
- अब परिणाम को result = result - removeSubarr(arr1, len1) से अपडेट करें।
- अब परिणाम दोनों शर्तों को पूरा करने वाली उपसरणियों को समाहित करता है।
- परिणाम फिर से प्रिंट करें।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
// शर्त 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