আমাদের একটি ইন্টিজার অ্যারে দেওয়া আছে। লক্ষ্য হল এমন সাব-অ্যারেগুলোর সংখ্যা বের করা যাদের এলিমেন্টগুলো পুনর্বিন্যাস করে একটি বৈধ প্যালিনড্রোম তৈরি করা সম্ভব। প্যালিনড্রোম বলতে শুরুর থেকে এবং শেষ থেকে পড়লে একই অনুক্রম পাওয়া যায় এমন সিকোয়েন্সকে বোঝায়।
উদাহরণ
ইনপুট: arr[] = {3, 3, 1, 4, 2, 1, 5}
আউটপুট: ৯
ব্যাখ্যা: বৈধ সাব-অ্যারে: {3}, {3}, {1}, {4}, {2}, {1}, {5}, {1,2,1}, {1,3,1}।
ইনপুট: arr[] = {2, 5, 5, 2, 1}
আউটপুট: ৮
ব্যাখ্যা: বৈধ সাব-অ্যারে: {2}, {5}, {5}, {2}, {1}, {5,2,5}, {2,5,2}, {2,5,5,2}।
অ্যালগরিদম (বিটমাস্ক ব্যবহার করে)
একটি সাব-অ্যারের এলিমেন্টগুলো প্যালিনড্রোম বানাতে পারবে যদি তার ফ্রিকোয়েন্সি কাউন্টে সর্বোচ্চ একটি অড (odd) ফ্রিকোয়েন্সি থাকে। এটি বিটমাস্ক দিয়ে দক্ষতার সাথে চেক করা যায়। প্রতিটি সংখ্যা x-র জন্য বিটমাস্কে (1LL << x) ব্যবহার করা হয়। XOR অপারেশন দিয়ে ফ্রিকোয়েন্সি প্যারিটি ট্র্যাক করা হয়। যদি বিটমাস্ক ০ হয় বা শুধু একটি বিট সেট থাকে (temp & (temp-1) == 0), তবে সেটি প্যালিনড্রোম বানাতে পারবে।
- প্রতিটি সাব-অ্যারে জন্য বিটমাস্ক
temp = 0দিয়ে শুরু করুন। - প্রতিটি এলিমেন্ট
arr[j]যোগ করার সময়temp ^= (1LL << arr[j])করুন। - যদি
temp == 0বাcheck(temp)সত্য হয় (শুধু একটি বিট সেট), তবে কাউন্ট বাড়ান। check(temp)ফাংশন:return !(temp & (temp - 1))।
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
bool check(long long temp) {
return !(temp & (temp - 1LL));
}
int palindromes_rearrange(int arr[], int size) {
int count = 0;
for (int i = 0; i < size; i++) {
long long temp = 0LL;
for (int j = i; j < size; j++) {
long long val = 1LL << arr[j];
temp ^= val;
bool ch = check(temp);
if (temp == 0LL || ch) count++;
}
}
return count;
}
int main() {
int arr[] = {3, 3, 1, 4, 2, 1, 5};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Count of sub-arrays whose elements can be re-arranged to form palindromes are: "
<< palindromes_rearrange(arr, size);
return 0;
}
আউটপুট
Count of sub-arrays whose elements can be re-arranged to form palindromes are: 9
