সমস্যা বিবৃতি
N সংখ্যার একটি অ্যারে দেওয়া, কাজটি হল একই সংখ্যক সেট বিটের সাথে সংখ্যা যোগ করার মাধ্যমে সর্বাধিক যোগফল খুঁজে পাওয়া
উদাহরণ
যদি ইনপুট অ্যারে হয় {2, 5, 8, 9, 10, 7} তাহলে আউটপুট হবে 14 −
-
2-এ সেট বিটের সংখ্যা হল 1
-
5 এ সেট বিটের সংখ্যা হল 2
-
8 এ সেট বিটের সংখ্যা হল 1
-
9-এ সেট বিটের সংখ্যা হল 2
-
10-এ সেট বিটের সংখ্যা হল 2
-
7-এ সেট বিটের সংখ্যা হল 3
তারপর (5 + 9 + 10) এর যোগফল হল 24 যার সেট বিটের সংখ্যা =2
অ্যালগরিদম
-
অ্যারেতে যান এবং প্রতিটি উপাদানের জন্য সেট বিটের সংখ্যা গণনা করুন।
-
32 বিটের জন্য একটি অ্যারে শুরু করুন, সংখ্যাটি সর্বাধিক 32 সেট বিট রয়েছে বলে ধরে নিয়ে৷
-
অ্যারেতে পুনরাবৃত্তি করুন এবং অ্যারে উপাদানটিকে সেই অবস্থানে যুক্ত করুন যা সেট বিটের সংখ্যা নির্দেশ করে৷
-
অতিক্রম করুন এবং সর্বাধিক যোগফল খুঁজে বের করুন এবং ফেরত দিন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int bitCount(int n){
int count = 0;
while (n) {
count++;
n = n & (n - 1);
}
return count;
}
int maxSum(int arr[], int n){
int bits[n];
for (int i = 0; i < n; i++) {
bits[i] = bitCount(arr[i]);
}
int sum[32] = { 0 };
for (int i = 0; i < n; i++) {
sum[bits[i]] += arr[i];
}
int maximum = 0;
for (int i = 0; i < 32; i++) {
maximum = max(sum[i], maximum);
}
return maximum;
}
int main(){
int arr[] = {2, 5, 8, 9, 10, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sum = " << maxSum(arr, n) << endl;
return 0;
} আউটপুট
আপনি যখন উপরের প্রোগ্রামটি কম্পাইল এবং এক্সিকিউট করবেন। এটি অনুসরণ করে আউটপুট −
তৈরি করেMaximum sum = 24
