เพิ่ม Bitwise OR ของอาร์เรย์ใน C++

โจทย์

ได้รับอาร์เรย์ N จำนวนเต็ม ต้องเพิ่ม Bitwise OR ของทุกองค์ประกอบให้มากที่สุด โดยทำหนึ่งงาน: คูณองค์ประกอบใดองค์ประกอบหนึ่งได้สูงสุด k ครั้งด้วยจำนวนเต็ม x ที่กำหนด

ถ้าอินพุตอาร์เรย์คือ {4, 3, 6, 1}, k = 2, x = 3 ค่าสูงสุดที่ได้คือ 55

อัลกอริทึม

1. คูณอาร์เรย์ element ด้วย (x^k) และ Bitwise OR กับ Prefix OR ของทุก element ก่อนหน้า
2. คูณอาร์เรย์ element ด้วย Bitwise OR ของทุก element ถัดไป
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