Tối đa hóa OR theo từng bit của một mảng trong C ++

Tuyên bố vấn đề

Cho một mảng gồm N số nguyên. OR theo chiều bit của tất cả các phần tử của mảng phải được tối đa hóa bằng cách thực hiện một tác vụ. Nhiệm vụ là nhân bất kỳ phần tử nào của mảng tối đa k lần với một số nguyên x

Nếu mảng đầu vào là {4, 3, 6, 1}, k =2 và x =3 thì giá trị lớn nhất có thể nhận được là 55

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau−

Result = 55