C++ में ऐरे के बिटवाइज OR को अधिकतम करना

समस्या कथन

N पूर्णांकों का एक ऐरे दिया गया है। ऐरे के सभी तत्वों के बिटवाइज OR को एक कार्य करके अधिकतम करना है। कार्य ऐरे के किसी भी तत्व को अधिकतम k बार दिए गए पूर्णांक x से गुणा करना है।

यदि इनपुट ऐरे है {4, 3, 6, 1}, k = 2 और x = 3 तो प्राप्त किया जा सकने वाला अधिकतम मान 55 है।

एल्गोरिदम

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