C++ में समान संख्या में सम और विषम तत्वों वाले सबएरे की गिनती

हमें धनात्मक पूर्णांकों की एक सरणी दी गई है। लक्ष्य सरणी में संख्याओं के उन सबएरे को ढूंढना है जिनमें प्रत्येक सबएरे में सम और विषम तत्वों की संख्या समान हो। यदि सरणी {1,2,3,4} है। तो सबएरे होंगे {1,2}, {2,3}, {3,4}, {1,2,3,4}। ऐसे सबएरे की संख्या 4 है।

उदाहरण सहित समझ

इनपुट - arr[] = {1,3,5,7,8,3,2 };

आउटपुट - समान सम और विषम तत्वों वाले सबएरे की संख्या: 4

व्याख्या - सबएरे होंगे: {7,8}, {8,3}, {3,2}, {7,8,3,2}

इनपुट - arr[] = {2,4,6 };

आउटपुट - समान सम और विषम तत्वों वाले सबएरे की संख्या: 0

व्याख्या - सभी तत्व सम हैं।

प्रोग्राम में उपयोग किया गया दृष्टिकोण

इस दृष्टिकोण में, हम एक चर temp का उपयोग करेंगे जो सरणी तत्वों का अंतर है (प्रारंभ में 0) और यदि arr[i] विषम है तो इसे 1 से बढ़ाएँ और यदि arr[i] सम है तो 1 से घटाएँ। जब temp का मान स्वयं को दोहराता है तो इन इंडेक्स के बीच समान संख्या में सम-विषम संख्याओं वाला एक सबएरे अवश्य मौजूद होगा। temp धनात्मक और ऋणात्मक दोनों हो सकता है। धनात्मक अंतर की आवृत्ति के लिए दो हैश सरणी arr_1[size+1] और ऋणात्मक अंतर की आवृत्ति के लिए arr_2[size+1] लेना।

प्रत्येक अंतर temp < 0 के लिए arr_1[-temp] से आवृत्ति को काउंट में जोड़ें। [ -(-temp) ] धनात्मक इंडेक्स देता है।

प्रत्येक अंतर temp > 0 के लिए arr_2[temp] से आवृत्ति को काउंट में जोड़ें। चूंकि समान अंतर मान की सभी घटनाएं सबएरे का हिस्सा होंगी। इन आवृत्तियों को 1 से अपडेट करें।

Arr[] = { 1,3,5,7,8,3,2 }
Temp मान 0 से शुरू होकर:
1,2,3,4,3,4,3
arr_1[] { 1,1,1,3,2,0,0,0 } // सभी अंतर धनात्मक हैं
arr_2[] { 0,0,0,0,0,0,0,0 } // कोई अंतर ऋणात्मक नहीं है
प्रत्येक पुनरावृत्ति में arr_1[temp] को काउंट में जोड़ने से काउंट=4 मिलता है।
सबएरे हैं: {7,8}, {8,3}, {3,2}, {7,8,3,2}

• प्रारंभिक सरणी को arr[] के रूप में लें।
• फंक्शन Sub_even_odd(int arr[], int size) सरणी और इसकी लंबाई लेता है और समान सम और विषम तत्वों वाले सबएरे की संख्या लौटाता है।
• प्रारंभिक काउंट 0 और चर temp लें जो विषम मान मिलने पर बढ़ता है और सम मान मिलने पर घटता है।
• दो सरणी arr_1[] और arr_2[] लें temp की आवृत्तियों को संग्रहीत करने के लिए। arr_1[] धनात्मक temp मानों के लिए जो पूरे सरणी के सम होने पर size+1 तक हो सकते हैं। arr_2[] ऋणात्मक temp मानों के लिए जो पूरे सरणी के विषम होने पर size+1 तक हो सकते हैं।
• फॉर लूप का उपयोग करके arr[] को ट्रैवर्स करें।
• यदि arr[i] & 1 == 1 तो arr[i] विषम है। temp बढ़ाएँ। अन्यथा temp घटाएँ।
• यदि temp < 0 तो arr_2[] से संबंधित आवृत्ति को काउंट में जोड़ें। उस आवृत्ति को 1 से बढ़ाएँ।
• यदि temp > 0 तो arr_1[] से संबंधित आवृत्ति को काउंट में जोड़ें। उस आवृत्ति को 1 से बढ़ाएँ।
• अंत में, हमारे पास arr[] में उन सबएरे की संख्या है जिनमें समान संख्या में सम और विषम तत्व हैं।
• परिणाम के रूप में काउंट लौटाएँ।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

int Sub_even_odd(int arr[], int size) {
    int count = 0;
    int temp = 0;
    int arr_1[size + 1] = {0};
    int arr_2[size + 1] = {0};
    arr_1[0] = 1;
    for (int i = 0; i < size; i++) {
        if (arr[i] & 1 == 1) {
            temp++;
        } else {
            temp--;
        }
        if (temp < 0) {
            count += arr_2[-temp];
            arr_2[-temp]++;
        } else {
            count += arr_1[temp];
            arr_1[temp]++;
        }
    }
    return count;
}

int main() {
    int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of subarrays with same even and odd elements are: " << Sub_even_odd(arr, size);
    return 0;
}

आउटपुट

Count of subarrays with same even and odd elements are: 4