Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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

हमें एक सरणी 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
  1. - C++ में बिट्स को पुनर्व्यवस्थित करके संख्या को अधिकतम करना

    समस्या कथन एक अनसाइन्ड संख्या दी गई है, दी गई अनसाइन्ड संख्या के बिट्स का उपयोग करके बनाई जा सकने वाली अधिकतम संख्या ढूंढें। यदि इनपुट संख्या 8 है तो इसका बाइनरी प्रतिनिधित्व है: 00000000000000000000000000001000 इसे अधिकतम करने के लिए MSB को 1 पर सेट करें। तब संख्या 2147483648 बन जाती है जिसका बा

  1. - C++ में ऐरे के बिटवाइज OR को अधिकतम करना

    समस्या कथन N पूर्णांकों का एक ऐरे दिया गया है। ऐरे के सभी तत्वों के बिटवाइज OR को एक कार्य करके अधिकतम करना है। कार्य ऐरे के किसी भी तत्व को अधिकतम k बार दिए गए पूर्णांक x से गुणा करना है। यदि इनपुट ऐरे है {4, 3, 6, 1}, k = 2 और x = 3 तो प्राप्त किया जा सकने वाला अधिकतम मान 55 है। एल्गोरिदम 1. एक

  1. - C++ में सबएरे फ्लिप करके 0 की संख्या को अधिकतम करना

    समस्या कथन एक बाइनरी ऐरे दिया गया है, एक सबएरे के एक फ्लिप की अनुमति के साथ ऐरे में अधिकतम शून्य की संख्या ढूंढें। एक फ्लिप ऑपरेशन सभी 0 को 1 में और 1 को 0 में बदल देता है। यदि arr1 = {1, 1, 0, 0, 0, 0, 0} यदि हम पहले 2 1 को 0 में फ्लिप करते हैं, तो हम आकार 7 का सबएरे प्राप्त कर सकते हैं: {0, 0, 0