C++에서 배열의 비트 OR 최대화

문제 설명

N개의 정수 배열이 주어집니다. 배열의 모든 요소에 대한 비트 OR은 하나의 작업을 수행하여 최대화되어야 합니다. 작업은 배열의 모든 요소에 주어진 정수 x를 최대 k번 곱하는 것입니다.

입력 배열이 {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