সমস্যা বিবরণ
N ইন্টিজারের একটি অ্যারে দেওয়া আছে। অ্যারে-এর সব উপাদানের বিটওয়াইজ OR কে একটি টাস্ক দিয়ে সর্বাধিক করতে হবে। টাস্ক হল অ্যারে-এর যেকোনো একটি উপাদানকে সর্বোচ্চ k বার একটি দেওয়া ইন্টিজার x দিয়ে গুণ করা।
যদি ইনপুট অ্যারে হয় {4, 3, 6, 1}, k = 2 এবং x = 3 তবে সর্বোচ্চ মান যা পাওয়া যায় ৫৫।
অ্যালগরিদম
1. একটি অ্যারে উপাদানকে (x^k) দিয়ে গুণ করুন এবং সেটি পূর্বের সব উপাদানের বিটওয়াইজ OR দিয়ে OR করুন। 2. একটি অ্যারে উপাদানকে পরবর্তী সব উপাদানের বিটওয়াইজ OR দিয়ে গুণ করুন। 3. সব ইটারেশনের পর সর্বোচ্চ মান রিটার্ন করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int getMaxOr(int* arr, int n, int k, int x) {
int prefixSum[n + 1];
int suffixSum[n + 1];
int power = 1;
for (int i = 0; i < k; ++i) power = power * x;
prefixSum[0] = 0;
for (int i = 0; i < n; ++i) prefixSum[i + 1] = prefixSum[i] | arr[i];
suffixSum[n] = 0;
for (int i = n - 1; i >= 0; --i) suffixSum[i] = suffixSum[i + 1] | arr[i];
int result = INT_MIN;
for (int i = 0; i < n; ++i) {
result = max(result, prefixSum[i] | (arr[i] * power) | suffixSum[i + 1]);
}
return result;
}
int main() {
int arr[] = {4, 3, 6, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
int x = 3;
cout << "Result = " << getMaxOr(arr, n, k, x) << endl;
return 0;
}
আউটপুট
Result = 55
