আমাদের একটি আনসর্টেড ইন্টিজার অ্যারে দেওয়া আছে। কাজ হলো দুটি জিনিস নির্ণয় করা: (১) একই সংখ্যক সেট বিট वाले উপাদান এবং (২) সেই উপাদানগুলো অ্যারেতে কন্টিগুয়াস (সান্নিহিত) অবস্থানে থাকতে হবে।
ইনপুট
int arr[] = { 5, 8, 1, 2, 9, 12}
আউটপুট: একই সংখ্যক সেট বিট 가진 সর্বোচ্চ সংখ্যক কন্টিগুয়াস অ্যারে উপাদান - 3
ব্যাখ্যা: অ্যারের প্রতিটি উপাদানের বাইনারি রিপ্রেজেন্টেশন এবং সেট বিট গণনা:
arr[0] = 5 => 0101 => সেট বিট: 2 arr[1] = 8 => 1000 => সেট বিট: 1 arr[2] = 1 => 0001 => সেট বিট: 1 arr[3] = 2 => 0010 => সেট বিট: 1 arr[4] = 9 => 1001 => সেট বিট: 2 arr[5] = 12 => 1100 => সেট বিট: 2
একই সংখ্যক সেট বিট (২) এবং কন্টিগুয়াস অবস্থানে থাকা উপাদানগুলো হলো 5, 9 এবং 12। তাই সর্বোচ্চ সংখ্যা ৩।
ইনপুট: int arr[] = { 5, 8, 1, 2}
আউটপুট: একই সংখ্যক সেট বিট 가진 সর্বোচ্চ সংখ্যক কন্টিগুয়াস অ্যারে উপাদান - 2
ব্যাখ্যা: এখানে 1 এবং 2 দুটো উপাদানের সেট বিট ১ এবং এগুলো কন্টিগুয়াস। তাই সর্বোচ্চ সংখ্যা ২।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- ইন্টিজার টাইপের অ্যারে উপাদান ইনপুট নেওয়া।
- size() ফাংশন দিয়ে অ্যারের আকার নির্ণয় করে ফাংশনে পাস করা।
- temp = 1 এবং maximum = 1 ইনিশিয়ালাইজ করা।
- vector
vec ডিক্লেয়ার করা। - 0 থেকে size-1 পর্যন্ত লুপে প্রতিটি উপাদানের সেট বিট __builtin_popcount() দিয়ে গণনা করে vec-এ স্টোর করা।
- 1 থেকে vec.size()-1 পর্যন্ত লুপে vec[i] == vec[i-1] কিনা চেক করা (সদ্য দিয়ে যাওয়ায় i+1 বাদ দিয়ে i-1 দিয়ে চেক করা উচিত)।
- যদি সমান হয় তবে temp++ আর না হলে temp = 1।
- maximum = max(maximum, temp) আপডেট করা।
- maximum রিটার্ন করা।
- ফলাফল প্রিন্ট করা।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int maximum_SameBits(int arr[], int size){
int temp = 1;
int maximum = 1;
vector vec;
for (int i = 0; i < size; i++){
vec.push_back(__builtin_popcount(arr[i]));
}
for (int i = 1; i < vec.size(); i++){
if (vec[i] == vec[i-1]){
temp++;
}
else{
temp = 1;
}
maximum = max(maximum, temp);
}
return maximum;
}
int main(){
int arr[] = { 5, 8, 1, 2, 9, 12};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum number of contiguous array elements with same number of set bits are: " << maximum_SameBits(arr, size);
return 0;
} আউটপুট
Maximum number of contiguous array elements with same number of set bits are: 3
