আমাদের একটি অ্যারে দেওয়া হয়েছে 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[] নিন এবং এর দৈর্ঘ্য গণনা করুন।
-
ফাংশন রিমুভ সাবার (int arr[], int len) সাবয়ারের গণনা প্রদান করে যা সন্তোষজনক নয় শর্ত 2।
-
0 হিসাবে প্রাথমিক গণনা নিন।
-
লুপ ব্যবহার করে পুনরাবৃত্ত বিন্যাস এবং ভেরিয়েবল যোগফল এবং ম্যাক্সভ্যাল নিন।
-
60 সাবয়ারের রেঞ্জে পুনরাবৃত্তি করার জন্য আরেকটি লুপ নিন কারণ 60-এর বেশি শর্ত 2 কখনই মিথ্যা হতে পারে না।
-
যোগফলের সাথে উপাদান যোগ করুন এবং সর্বোচ্চ maxVal এ নিন।
-
যদি যোগফল জোড় হয় এবং 2 * maxVal> যোগফল হয় তাহলে শর্ত 2 পূরণ হয় না বলে ইনক্রিমেন্ট গণনা।
-
উভয় লুপের শেষে গণনা ফেরত দেয়।
-
ফাংশন findSubarrays(int arr1[], int len1) একটি ইনপুট অ্যারে এবং এর দৈর্ঘ্য নেয় এবং উপরে উল্লিখিত উভয় শর্ত পূরণ করে সাব্যারেগুলির গণনা প্রদান করে৷
-
শুধুমাত্র শর্ত 1 অনুসরণ করে এমন সাবয়ারের গণনা গণনা করতে একটি প্রিফিক্স অ্যারে নিন।
-
লুপ ব্যবহার করে ট্রাভার্স অ্যারে এবং __builtin_popcountll(arr1[i]) দিয়ে প্রতিটি উপাদান সেট করুন যা এতে সেট বিটের সংখ্যা।
-
লুপের জন্য উপসর্গ অ্যারে তৈরি করুন এবং উপসর্গ [i] =উপসর্গ[i] + উপসর্গ[i - 1] সেট করুন যেখানে প্রথম উপাদান ছাড়া।
-
উপসর্গ অ্যারেতে বিজোড় এবং জোড় মান গণনা করুন।
-
tmp1=( oddcount * (oddcount-1) )/2 এবং tmp2=( evencount * (evencount-1) )/2 সেট করুন এবং উভয়ের যোগফল হিসাবে ফলাফল করুন।
-
ফলাফল সাবয়ারের সন্তোষজনক শর্ত 1 এর যোগফল হবে।
-
প্রিন্ট ফলাফল।
-
এখন ফলাফল আপডেট করুন ফলাফল =ফলাফল - রিমুভ সুবার (আর 1, লেন1)।
-
এখন ফলাফল উভয় শর্ত সন্তুষ্ট subarray রয়েছে.
-
ফলাফল আবার প্রিন্ট করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
// Function to count subarrays not satisfying condition 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
