C++-এ XOR শূন্য যেসব সাবঅ্যারে তাদের সংখ্যা সর্বাধিক করা

আমাদের একটি Arr[] অ্যারে দেওয়া আছে যাতে পূর্ণসংখ্যা মান রয়েছে। লক্ষ্য হল XOR ০ যেসব সাবঅ্যারে তাদের সর্বাধিক সংখ্যা খুঁজে বের করা। যেকোনো সাবঅ্যারের বিটগুলো যেকোনো সংখ্যক বার সোয়াপ করা যেতে পারে।

নোট:- 1 <= Arr[i] <= 10¹⁸

বিট সোয়াপ করে যেকোনো সাবঅ্যারের XOR ০ করার জন্য দুটি শর্ত পূরণ করতে হবে:-

যদি লেফট থেকে রাইট রেঞ্জে সেট বিটের সংখ্যা সম হয়।
যেকোনো দেওয়া রেঞ্জের জন্য বিটের যোগফল <= ২ (সেট বিটে সর্বোচ্চ সংখ্যা)

বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি দেখে নিই -

ইন - Arr[] = { 1,2,5,4 }

আউট -

শুধু ১ম শর্ত পূরণকারী সাবঅ্যারে: ৪

উভয় শর্ত পূরণকারী সাবঅ্যারে: ৩

ইন - Arr[] = { 3,7,2,9 }

আউট -

শুধু ১ম শর্ত পূরণকারী সাবঅ্যারে: ৬

উভয় শর্ত পূরণকারী সাবঅ্যারে: ৩

নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি -

এই পদ্ধতিতে আমরা পর্যবেক্ষণ করেছি যে বিট সোয়াপ করে যেকোনো সাবঅ্যারের XOR ০ করার জন্য দুটি শর্ত পূরণ করতে হবে:- যদি লেফট থেকে রাইট রেঞ্জে সেট বিটের সংখ্যা সম হয় অথবা যেকোনো দেওয়া রেঞ্জের জন্য বিটের যোগফল <= ২ (সেট বিটে সর্বোচ্চ সংখ্যা)

ইনপুট অ্যারে Arr[] নিন এবং এর লেনথ গণনা করুন।
removeSubarr(int arr[], int len) ফাংশনটি শর্ত ২ পূরণ না করা সাবঅ্যারের কাউন্ট রিটার্ন করে।
প্রাথমিক কাউন্ট ০ হিসেবে নিন।
ফর লুপ ব্যবহার করে অ্যারে ইটারেট করুন এবং sum এবং maxVal ভেরিয়েবল নিন।
আরেকটি ফর লুপ ব্যবহার করে ৬০টি সাবঅ্যারে পর্যন্ত ইটারেট করুন কারণ ৬০-এর পরে শর্ত ২ কখনো false হতে পারে না।
সাম তে উপাদান যোগ করুন এবং maxVal-এ সর্বোচ্চ মান নিন।
যদি sum সম হয় এবং 2 * maxVal > sum হয় তবে কাউন্ট বাড়ান কারণ শর্ত ২ পূরণ হয়নি।
দুটি লুপের শেষে count রিটার্ন করুন।
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 হবে শুধু শর্ত ১ পূরণকারী সাবঅ্যারের যোগফল।
Result প্রিন্ট করুন।
এখন result আপডেট করুন result = result - removeSubarr(arr1, len1) দিয়ে।
এখন result উভয় শর্ত পূরণকারী সাবঅ্যারে ধারণ করে।
আবার result প্রিন্ট করুন।

উদাহরণ

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

// শর্ত ২ পূরণ না করা সাবঅ্যারের কাউন্ট করার ফাংশন
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