C++で配列のビットごとのORを最大化する

N個の整数の配列が与えられます。配列のすべての要素のビットごとのORは、1つのタスクを実行することによって最大化する必要があります。タスクは、配列の任意の要素に、指定された整数x

入力配列が{4、3、6、1}、k =2、x =3の場合、取得できる最大値は55

アルゴリズム

1. multiply an array element with (x^k) and do bitwise OR it with the bitwise OR of all previous elements
2. Multiply an array element with bitwise OR of all next elements
3. Return the maximum value after all iterations

例

#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