उन उप-सरणियों की गणना जिनके तत्वों को पुनर्व्यवस्थित करके पालिंड्रोम बनाया जा सके - C++ प्रोग्राम

समस्या विवरण

हमें एक पूर्णांक ऐरे दिया गया है। लक्ष्य उन उप-सरणियों की गणना करना है जिनके तत्वों को पुनर्व्यवस्थित करके एक वैध पालिंड्रोम बनाया जा सके। पालिंड्रोम वे अनुक्रम होते हैं जो शुरुआत और अंत से समान पढ़े जाते हैं।

उदाहरण

इनपुट: arr[] = {3, 3, 1, 4, 2, 1, 5}

आउटपुट: 9

व्याख्या: वैध उप-सरणियाँ: {3}, {3}, {1}, {4}, {2}, {1}, {5}, {1,2,1}, {1,3,1}। कुल 9।

इनपुट: arr[] = {2, 5, 5, 2, 1}

आउटपुट: 8

व्याख्या: वैध उप-सरणियाँ: {2}, {5}, {5}, {2}, {1}, {5,2,5}, {2,5,2}, {2,5,5,2}। कुल 8।

दृष्टिकोण

एक उप-सरणी को पालिंड्रोम में पुनर्व्यवस्थित किया जा सकता है यदि अधिकतम एक तत्व की आवृत्ति विषम हो। हम बिटमास्क का उपयोग करके प्रत्येक उप-सरणी के लिए विषम आवृत्तियों की समता को ट्रैक करते हैं।

• प्रत्येक मान arr[j] के लिए बिट arr[j] को टॉगल करें (XOR ऑपरेशन)
• यदि परिणाम 0 है (सभी आवृत्तियाँ सम) या केवल एक बिट सेट है (एक विषम आवृत्ति), तो यह वैध है
• check(x) फंक्शन जाँचता है कि x & (x-1) == 0 (अधिकतम एक बिट सेट)

एल्गोरिदम

1. प्रारंभिक count = 0
2. प्रत्येक प्रारंभिक इंडेक्स i के लिए:
   • temp = 0 (बिटमास्क)
   • प्रत्येक अंतिम इंडेक्स j >= i के लिए:
     • val = 1LL << arr[j]
     • temp ^= val
     • यदि temp == 0 || check(temp) तो count++
3. count लौटाएँ

C++ कार्यान्वयन

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

bool check(long long mask) {
    return (mask & (mask - 1)) == 0;
}

int palindromes_rearrange(int arr[], int size) {
    int count = 0;
    for (int i = 0; i < size; i++) {
        long long temp = 0;
        for (int j = i; j < size; j++) {
            long long val = 1LL << arr[j];
            temp ^= val;
            if (temp == 0 || check(temp)) count++;
        }
    }
    return count;
}

int main() {
    int arr[] = {3, 3, 1, 4, 2, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count: " << palindromes_rearrange(arr, size);
    return 0;
}

आउटपुट

Count: 9