You have given an array A containing N integers. You can do the following operation at most K times:
• Choose any index i and increase the value of At by 1.
Your task is to find the maximum bitwise OR of the array.
Input format
• The first line contains an integer T denoting the number of test cases.
• The first line of each test case contains two space-separated integers N and K.
• The second line of each test case contains N space-separated integers denoting array A.
Output format
For each test case, print the maximum possible bitwise OR of the array after performing at most K operations in a new line.
Constraints
1 ≤ T ≤ 100000 1 ≤ N ≤ 200000
O ≤ K ≤ le18
It is guaranteed that the sum of N over T test cases does not exceed le6.
Explanation
For the first test case, we can increase the value of the 5-th index by 2. Thus the A becomes {1, 3, 7, 0, 8, 1}. The bitwise OR of array A becomes 15.
#include <bits/stdc++.h>
using namespace std;
int minSum(int a[], int n, int k)
{
priority_queue <int> q;
for(int i = 0; i < n; i++)
{
q.push(a[i]);
}
while(!q.empty() && k > 0)
{
int top = q.top() / 2;
q.pop();
q.push(top);
k -= 1;
}
int sum = 0;
while(!q.empty())
{
sum += q.top();
q.pop();
}
return sum;
}
int main()
{
int n = 4;
int k = 3;
int a[] = { 20, 7, 5, 4 };
cout << (minSum(a, n, k));
return 0;
}
Comments
Leave a comment